数据结构之二叉树及其应用
二叉树及其应用
1.用递归和非递归两种方式实现先序，中序，后序遍历
（1）递归：
递归序：每个节点会三次回到自己，在此基础上引申出了先序，中序，和后序遍历
①先序遍历（头左右）：在递归序的基础上，第一次出现时打印（或进行操作）
public static void preOrderRecur(Node head){
if(head == null){
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
②中序遍历（左头右）：在递归序的基础上，第二次出现时打印（或进行操作）
public static void inOrderRecur(Node head){
if(head == null){
return;
}
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
③后序遍历（左右头）：在递归序的基础上，第三次出现时打印（或进行操作）
public static void posOrderRecur(Node head){
if(head == null){
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}
（2）非递归：
①先序遍历（同上）：
第一步：从栈中弹出一个节点car；
第二步：打印（或处理）car；
第三步：先压右再压左（如果有的话），没有就不操作；
第四步：重复上述步骤；
public static void preOrderUnRecur(Node head){
if(head != null){
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while(!stack.isEmpty()){
head = stack.pop();
System.out.print(head.value + " ");
if(head.right != null){
stack.push(head.right);
}
if(head.left != null){
stack.push(head.left);
}
}
}
System.out.println();
}
②中序遍历（同上）：
第一步：对于每一颗子树，左边界全部进栈（从父到子）；
第二步：依次弹出的过程中，打印；
第三步：弹出节点的右树重复上述步骤（如果有的话）；
public static void inOrderUnRecur(Node head){
if(head != null){
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.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
③后序遍历（同上）：（略有不同的地方是，用了两个栈）
此方法本质（个人理解）：利用栈的特点，从头右左的遍历顺序逆序出栈，变成左右头。
第一步：从栈中弹出一个节点car；
第二步：car放入收集栈；
第三步：先压左再压右；
第四步：重复上述步骤；
public static void posOrderUnRecur(Node head){
if(head != null){
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(head);
while(!s1.isEmpty()){
head = s1.pop();
s2.push(head);
if(head.left != null){
s1.push(head.left);
}
if(head.right != null){
s1.push(head.right);
}
}
while(!s2.isEmpty()){
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
所有方法的运行截图：
2.完成二叉树的宽度优先遍历（宽度遍历用队列）
二叉树的深度优先遍历即是先序遍历；
①从队列弹出一个节点；
②先放左，再放右；
public static void widthFirstOrder(Node head){
if(head == null){
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
Node cur = queue.poll();
System.out.println(cur.value);
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
}
}
3.二叉树的相关概念
-
①搜索二叉树（BST）：对于每一棵子树，它的左树都比它小，右树都比它大；
②如何判断搜索二叉树：中序遍历，如果某个位置存在降序，则不是搜索二叉树，即搜索二叉树中序遍历结果一定是升序；
第一种代码：
public static int preValue = Integer.MIN_VALUE;//设置一个全局变量用来比较是否为升序；此语句意为整数（Integer）的最小值 public static boolean checkBST(Node head){ if(head == null){ return true;//如果树为空，认为是搜索二叉树 } boolean isLeftBST = checkBST(head.left);//判断左边是否为搜索二叉树，将结果返回给变量用于后续判断 if(!isLeftBST){ return false;//如果左边已经不为搜索二叉树，则直接返回false } if(head.value <= preValue){ return false;//如果左边树的最后一个节点比preValue小的话，则不为升序，直接返回false }else{ preValue = head.value;//如果大于的话，那就赋值给preValue，相当于将其作为指针遍历下去（个人理解） } return checkBST(head.right);//右树结果直接返回 }
第二种代码（运用递归思想）：
public static boolean isBST(Node head){
return process(head).isBST;
}
public static class ReturnData{
public boolean isBST;
public int min;
public int max;
public ReturnData(boolean is,int mi,int ma){
isBST = is;
min = mi;
max = ma;
}
}
public static ReturnData process(Node x){
if(x == null){
return null;
}
ReturnData leftData = process(x.left);
ReturnData rightData = process(x.right);
//找最值
int min = x.value;
int max = x.value;
if(leftData != null){
min = Math.min(min, leftData.min);
max = Math.max(max, leftData.max);
}
if(rightData != null){
min = Math.min(min, rightData.min);
max = Math.max(max, rightData.max);
}
//判断isBST
//第一种方法：
boolean isBST = true;
if(leftData!=null && (!leftData.isBST || leftData.max >= x.value)){
//如果左树有东西，且左树不为搜索二叉树，则直接false，或者如果左树有东西，且左树的最大值比根节点的值大，也直接 false
isBST = false;
}
if(rightData != null && (!rightData.isBST || x.value >= rightData.min)){
//同上面的思路，如果右树有东西，且右树不为搜索二叉树，则直接false，或者如果右树有东西，且右树的最小值比根节点的值 小，则直接false
isBST = false;
}
//第二种方法：
/*boolean isBST = false;
if(
(leftData!=null ? (leftData.isBST && leftData.max < x.value):true)
&&
(rightData != null ? (rightData.isBST && rightData.min > x.value) : true)
){
isBST = true;
}*/
return new ReturnData(isBST,min,max);//返回三个数据，是否为搜索二叉树，树的最小值与最大值
}
-
①完全二叉树（CBT）：每一层都是满的或者最后一层不满但从左到右是满的（比较拗口，建议去百度一手）
②如何判断完全二叉树：宽度优先遍历，（1）对于任意节点，如果有右无左直接false；（2）在（1）条件满足的情况下，如果第一次遇到了一个节点左右子不全（其实就是只有左节点或者本身为叶节点），那么后续节点必须全为叶节点（无子节点），如果不满足，则不为完全二叉树
public static boolean isCBT(Node head){ if(head == null){ return true; } LinkedList<Node> queue = new LinkedList<>(); boolean leaf = false; Node l = null; Node r = null; queue.add(head); while(!queue.isEmpty()){ head = queue.poll(); l = head.left; r = head.right; if((leaf && (l != null || r != null))||(l ==null && r != null)){ return false; } if(l != null){ queue.add(l); } if(r != null){ queue.add(r); } if(l == null || r == null){ leaf = true; } } return true; }
3.①满二叉树：一棵高度为h，并且含有2^h - 1个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点。满二叉树的叶子节点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2.(二叉树结点的度即为结点的孩子个数);
②如何判断满二叉树：可以直接根据定义，先求树的最大深度h，再求节点个数s，需要满足s=2^h-1;
public static boolean isFBT(Node head){
if(head == null){
return true;
}
ReturnData data = process(head);
return data.nodes == (1<<data.height - 1);
}
public static class ReturnData{
public static int height;
public static int nodes;
public ReturnData(int h,int n){
height = h;
nodes = n;
}
}
public static ReturnData process(Node x){
if(x == null){
return new ReturnData(0,0);
}
ReturnData leftData = process(x.left);
ReturnData rightData = process(x.right);
int height = Math.max(leftData.height,rightData.height)+1;
int nodes = leftData.nodes+rightData.nodes+1;
return new ReturnData(height,nodes);
}
4.①平衡二叉树（AVL）：对于任何一个子树，它的左树和右树高度差不超过1；
②如何判断平衡二叉树：首先需要满足根节点左树和右树都为平衡二叉树，再要满足左树的高度与右树的高度差不大于1；
public static boolean isBalanced(Node head){
return process(head).isBalanced;
}
public static class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isB,int hei){
isBalanced = isB;
height = hei;
}
}
public static ReturnType process(Node x){
if(x == null){
return new ReturnType(true,0);
}
ReturnType leftData = process(x.left);
ReturnType rightData = process(x.right);
int height = Math.max(leftData.height, rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height)<2;
return new ReturnType(isBalanced,height);
}
4.学习收获
二叉树的遍历是一个很常见的问题，也是学习数据结构和算法的基础。二叉树的遍历方式主要有：先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中，父节点先于它的子节点被访问，就是先序遍历；父节点被访问的次序位于左右孩子节点之间，就是中序遍历；访问完左右孩子节点之后再访问父节点，就是后序遍历。不论是先序遍历、中序遍历还是后序遍历，左右孩子节点的相对访问次序是不变的，总是先访问左孩子节点，再访问右孩子节点。而层次遍历，就是按照从上到下、从左向右的顺序访问二叉树的每个节点。
在学习二叉树的遍历时，我有以下几点收获：
- 二叉树的遍历可以通过递归和迭代两种方式实现。递归方式比较简单和直观，但是会占用较多的系统资源和栈空间。迭代方式需要借助其他数据结构，如栈或队列，来存储访问顺序和状态，但是效率更高。
- 二叉树的先序、中序和后序遍历都可以看作是对二叉树左侧链上的节点进行不同顺序的访问。先序遍历是自上而下地访问左侧链上的节点，并将右子树入栈暂存；中序遍历是自下而上地访问左侧链上的节点，并将当前节点入栈暂存；后序遍历是自下而上地访问左侧链上的节点，并将当前节点和右子树入栈暂存。
- 二叉树的层次遍历可以看作是对二叉树进行广度优先搜索（BFS）。需要使用一个队列来存储每一层的节点，并按照出队顺序依次访问。
- 二叉树的遍历有很多应用场景，如计算二叉树的高度、判断二叉树是否平衡、打印二叉树等。通过掌握不同的遍历方式，可以灵活地解决各种问题。
5.代码说明
这里的代码编写语言为Java，因为之前的c++版本代码找不到了，所以用了一下之前写的Java代码，虽然语言不同，但是我觉得对于二叉树的遍历这一思想是一样的，至少通过递归的方法思路完全一致。