数据结构:二叉树及相关算法
2021/12/25 22:07:23
本文主要是介绍数据结构:二叉树及相关算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉树
class Tree { Node left; Node right; int value; //递归 public static void f(Tree head) { if(head == null) { reutrn; } f(head.left); f(head.right); } //遍历结果 //1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1 }
遍历
先序遍历
先序遍历指的是所有子树中先打印头节点、在左节点、最后右节点
头左右::1,2,4,5,3,6,7(利用递归顺第一次出现的打印)
递归方式:
public static void f(Tree head) { if(head == null) { reutrn; } System.out.println(head.value); f(head.left); f(head.right); }
非递归压栈形式可实现:
每次
- 从栈中弹出一个节点cur
- 打印
- 先右后左压入(如果有)
- 重复1
public static void f(Tree head) { if(head == null) { return; } Stack<Node> stack = new Stack(); stack.add(head); while(!stack.isEmpty()){ Node head = stack.pop(); System.out.print(head.value); if(head.right != null) { stack.push(head.right); } if(head.left!= null) { stack.push(head.left); } } }
中序遍历
左头右:4,2,5,1,6,3,7(利用递归顺第二次出现的打印)
public static void f(Tree head) { if(head == null) { reutrn; } f(head.left); System.out.println(head.value); f(head.right); }
非递归:
- 先将所有子树左节点放入栈中
- 弹出打印
- 弹出时判断是否存在右子树
- 存在压入右节点
public void inOrderUnRecur(Node head) { if (head == null) { return; } Stack<Node> stack = new Stack<Node>(); while (!stack.isEmpty() || head != null) { if (head != null) { stack.push(head); head = head.left; } else { head = stack.pop(); System.out.println(head.value); head = head.right; } } }
后序遍历
左右头:4,5,2,6,7,3,1(利用递归顺第三次出现的打印)
public static void f(Tree head) { if(head == null) { reutrn; } f(head.left); f(head.right); System.out.println(head.value); }
非递归:
- 申请1个栈、1个收集栈
- 放入头cur 弹出放入收集栈
- 先左在右放入(如果右)
- 弹出
- 遍历收集栈
public static void f(Tree head) { if(head == null) { return; } Stack<Node> s1= new Stack(); Stack<Node> s2 = new Stack(); stack.push(head); while(!s1.isEmpty()){ head = s1.pop(); s2.push(head); if(head.left!= null) { stack.push(head.right); } if(head.right != null) { stack.push(head.right); } } while(!s2.isEmpty()){ System.out.println(s2.pop().value); } }
深度遍历
二叉树的深度遍历即为先序遍历。
广度遍历(宽度遍历)
用队列先左在右放入取出即可
public static void f(Node head) { if(head == null) { return; } Queue<Node> queue = new LinkedList<Node>(); queue.add(head); while(!queue.isEmpty()){ head= queue.poll(); System.out.print(head.value); if(head.left!= null) { queue.add(head.left); } if(head.right!= null) { queue.add(head.right); } } }
计算当前树最大宽度是多少
public static int w(Node head) { if(head == null) { return 0; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(head); //记录节点个数 Map<TreeNode, Integer> levelMap = new HashMap<>(); levelMap.put(head,1); //当前最大个数 int max = Integer.MIN_VALUE; //当前层数 int curLevel = 0; //当前节点个数统计 int curNodeNum = 0; while(!queue.isEmpty()){ head = queue.poll(); if (levelMap.get(head) == curLevel) { curNodeNum ++; } else { max = Math.max(max, curNodeNum); curLevel ++; curNodeNum = 1; } if(head.left!= null) { levelMap.put(head.left, curLevel + 1); queue.add(head.left); } if(head.right!= null) { levelMap.put(head.right, curLevel + 1); queue.add(head.right); } } return Math.max(max, curNodeNum); }
搜索二叉树
所有子树左节点都比右小
判断是否为搜索二叉树
中序遍历 判断是否为依次升序、升序即为搜索二叉树
public static boolean isBST(Tree head) { int preValue = 0; if(head == null) { reutrn true; } boolean result= isBST(head.left); if(!result){ return false; } if(head.value <= preValue) { return false; }else{ preValue = head.value; } return isBST(head.right); }
判断完全二叉树
- 进行广度遍历并记录
- 如果出现有右孩子无左孩子直接false
- 满足2条件如果出现第一个左右不全必须为叶子节点
这篇关于数据结构:二叉树及相关算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南