二叉树复习

现实生活中树

数据结构中树长这样子

二叉树的意思就是说：每个节点不能多于有两个儿子，上面的图就是一颗二叉树。

关键知识点

• 一棵树至少会有一个节点(根节点)
• 树由节点组成，每个节点的数据结构是这样的：
  
  节点的定义就是：一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)
• 二叉树第i层上的结点数目最多为2的（i-1）次方2^（i-1）(i>=1)
• 深度为k的二叉树至多有2k-1(k>=1)个结点

二叉树的遍历

四种主要的遍历思想为：
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
层次遍历：只需按层次遍历即可

静态创建二叉树

树是由若干个节点组成，节点连接起来就成了树，而节点由一个数据、两个指针组成
因此，创建树实际上就是创建节点，然后连接节点

举个栗子：这个二叉树为例来构建

定义节点类

package tree;
public class TreeNode {
    // 左节点(儿子)
    private TreeNode lefTreeNode;
    
    // 右节点(儿子)
    private TreeNode rightNode;
    
    // 数据
    private int value;
    
    public TreeNode() {
        super();
    }
    public TreeNode(int value) {
        super();
        this.value = value;
    }
    public TreeNode getLefTreeNode() {
        return lefTreeNode;
    }
    public void setLefTreeNode(TreeNode lefTreeNode) {
        this.lefTreeNode = lefTreeNode;
    }
    public TreeNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }   
}

创建上面二叉树代码

package tree;
public class TwoTreeDemo {
    public static void main(String[] args) {
        //先创建好这5个节点
        //根节点-->10
        TreeNode treeNode1 = new TreeNode(10);
        //左孩子-->9
        TreeNode treeNode2 = new TreeNode(9);
        //右孩子-->20
        TreeNode treeNode3 = new TreeNode(20);
        //20的左孩子-->15
        TreeNode treeNode4 = new TreeNode(15);
        //把他们连接起来
        //20的右孩子-->35
        TreeNode treeNode5 = new TreeNode(35);
      //根节点的左右孩子
        treeNode1.setLefTreeNode(treeNode2);
        treeNode1.setRightNode(treeNode3);
        //20节点的左右孩子
        treeNode3.setLefTreeNode(treeNode4);
        treeNode3.setRightNode(treeNode5);
    }
}

遍历代码

前序遍历10->9->20->15->35

public static void preTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问根节点
                System.out.println(rootTreeNode.getValue());
                //访问左节点
                preTraverseBTree(rootTreeNode.getLefTreeNode());
                //访问右节点
                preTraverseBTree(rootTreeNode.getRightNode());
            }
        }

前序遍历
中序遍历9->10->15->20->35

      public static void inTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问左节点
                inTraverseBTree(rootTreeNode.getLefTreeNode());
                //访问根节点
                System.out.println(rootTreeNode.getValue());
                //访问右节点
                inTraverseBTree(rootTreeNode.getRightNode());
            }
        }

后序遍历9->15->35->20->10

public static void endTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问左节点
                endTraverseBTree(rootTreeNode.getLefTreeNode());
                //访问右节点
                endTraverseBTree(rootTreeNode.getRightNode());
                //访问根节点
                System.out.println(rootTreeNode.getValue());
            }
        }

层序遍历10->9->20->15->35

public static void cengTraverseBTree(TreeNode rootTreeNode){
          //声明一个队列
          //LinkedBlockingQueue的容量是没有上限的,也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。
          //ArrayBlockingQueue在构造时需要指定容量
          Queue<TreeNode> queue = new LinkedBlockingQueue<>();      
            if (rootTreeNode == null) {
                return;
            }
            queue.add(rootTreeNode);
            while(!queue.isEmpty()) {
                TreeNode tempNode = queue.poll();
                System.out.println(tempNode.getValue());
                if(tempNode.getLefTreeNode()!=null)queue.add(tempNode.getLefTreeNode());
                if(tempNode.getRightNode()!=null)queue.add(tempNode.getRightNode());    
            }
        }

动态创建二叉树查找树

上面我们是手动创建二叉树的，一般地：都是给出一个数组给你，让你将数组变成一个二叉树，此时就需要我们动态创建二叉树了。
二叉树中还有一种特殊的二叉树：
二叉查找树(binary search tree)定义：
当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。
假设我们有一个数组：int[] arrays = {3, 2, 1, 4, 5};

1.首先将3作为根节点
2.随后2进来了，我们跟3做比较，比3小，那么放在3的左边
3.随后1进来了，我们跟3做比较，比3小，那么放在3的左边，此时3的左边有2了，因此跟2比，比2小，放在2的左边
4.随后4进来了，我们跟3做比较，比3大，那么放在3的右边
5.随后5进来了，我们跟3做比较，比3大，那么放在3的右边，此时3的右边有4了，因此跟4比，比4大，放在4的右边
#无论任何一颗子树，左边都比根要小，右边比根要大

代码实现

因为是动态创建的，因此我们得用一个类来表示根节点

package tree;
public class RootNode {
    private TreeNode treeRoot;
    public TreeNode getTreeRoot() {
        return treeRoot;
    }
    public void setTreeRoot(TreeNode treeRoot) {
        this.treeRoot = treeRoot;
    }
}

创建二叉搜索树代码

package tree;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class SerrchTwoTree {
    public static void main(String[] args) {
        int[] arrays = {3, 2, 1, 4, 5};
        RootNode root = new RootNode();
        for(int value:arrays) {
            createtree(root, value);
        }
        System.out.println("前序遍历");
        preTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("中序遍历");
        inTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("后序遍历");
        endTraverseBTree(root.getTreeRoot());
        System.out.println("");
        System.out.println("层序遍历");
        cengTraverseBTree(root.getTreeRoot());
    }
    //rootNode 根节点 v需要创造的节点的值
    public static void createtree(RootNode rootNode,int v) {
        //如果树根为空(第一次访问)，将第一个值作为根节点
        if(rootNode.getTreeRoot()==null) {
            TreeNode treeNode = new TreeNode(v);
            rootNode.setTreeRoot(treeNode);
        }else {
             //当前树根
            TreeNode tempNode = rootNode.getTreeRoot();
            while(tempNode!=null) {
                //当前值大于根值，往右边走
                if(v>tempNode.getValue()) {
                    //右边没有树根，那就直接插入 并且返回 记着返回哦
                    if(tempNode.getRightNode()==null) {
                        tempNode.setRightNode(new TreeNode(v));
                        return;
                    }else {
                        //如果右边有树根，到右边的树根去
                        tempNode = tempNode.getRightNode();
                    }
                }else {
                    if(tempNode.getLefTreeNode()==null) {
                        tempNode.setLefTreeNode(new TreeNode(v));
                        return;
                    }else {
                        tempNode=tempNode.getLefTreeNode();
                    }
                }
            }
        }
    }
    //前序遍历
      public static void preTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问根节点
                System.out.print(rootTreeNode.getValue()+" ");
                //访问左节点
                preTraverseBTree(rootTreeNode.getLefTreeNode());
                //访问右节点
                preTraverseBTree(rootTreeNode.getRightNode());
            }
        }
      //中序遍历
      public static void inTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问左节点
                inTraverseBTree(rootTreeNode.getLefTreeNode());
                //访问根节点
                System.out.print(rootTreeNode.getValue()+" ");
                //访问右节点
                inTraverseBTree(rootTreeNode.getRightNode());
            }
        }
    //后序遍历
      public static void endTraverseBTree(TreeNode rootTreeNode) {
            if (rootTreeNode != null) {
                //访问左节点
                endTraverseBTree(rootTreeNode.getLefTreeNode());
                //访问右节点
                endTraverseBTree(rootTreeNode.getRightNode());
                //访问根节点
                System.out.print(rootTreeNode.getValue()+" ");
            }
        }
      //层序遍历
      public static void cengTraverseBTree(TreeNode rootTreeNode){
          //声明一个队列
          //LinkedBlockingQueue的容量是没有上限的,也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。
          //ArrayBlockingQueue在构造时需要指定容量
          Queue<TreeNode> queue = new LinkedBlockingQueue<>();
            if (rootTreeNode == null) {
                return;
            }
            queue.add(rootTreeNode);
            while(!queue.isEmpty()) {
                TreeNode tempNode = queue.poll();
                System.out.print(tempNode.getValue()+" ");
                if(tempNode.getLefTreeNode()!=null)queue.add(tempNode.getLefTreeNode());
                if(tempNode.getRightNode()!=null)queue.add(tempNode.getRightNode());
            }
        }
}

结果

查询二叉树的深度

      public static int getHeight(TreeNode treeNode) {
            if (treeNode == null) {
                return 0; // 达到叶子返回0的孩子 然后递归回去加1
            } else {
                //左边的子树深度
                int left = getHeight(treeNode.getLefTreeNode());
                //右边的子树深度
                int right = getHeight(treeNode.getRightNode());
                int max = left;
                if (right > max) {
                    max = right;
                }
                return max + 1;
            }
        }
     // System.out.println(getHeight(treeNode1));

查询二叉树的最大值

如果是二叉查找树就是中序遍历的最后一个
步骤：

左边找最大值->递归
右边找最大值->递归
然后分别再与根节点的值比较

  public static int  getMax(TreeNode rootTreeNode) {
            if (rootTreeNode == null) {
                return -1;
            } else {
                //找出左边的最大值
                int left = getMax(rootTreeNode.getLefTreeNode());
                //找出右边的最大值
                int right = getMax(rootTreeNode.getRightNode());
                //与当前根节点比较
                int currentRootValue = rootTreeNode.getValue();
                //假设左边的最大
                int max = left;
                if (right > max) {
                    max = right;
                }
                if (currentRootValue > max) {
                    max = currentRootValue;
                }
                return max ;
            }
        }

前中/中后序重建二叉树

已知前序和中序遍历，可以确定一棵二叉树。
已知中序和后序遍历，可以确定一棵二叉树。
但是，已知前序和后序遍历，不能确定一棵二叉树。

已知前序和中序

步骤过程:

• 前序数组中最左边的值就是树的头节点值，记为h，并用h生成头节点，记为head，然后在中序数组中找到h，假设位置是i，那么在中序数组中，i左边的数组就是头节点左子树的中序数组，假设长度为l，则左子树的先序数组就是先序数组中h往右长度也为l的数组。

• 用左子树的先序和中序数组，递归整个过程建立左子树，返回的头节点记为left。

• i右边的数组就是头节点右子树的中序数组，假设长度为r，先序数组中右侧等长的部分就是头节点右子树的先序数组。

• 用右子树的先序和中序数组，递归整个过程建立右子树，返回的头节点记为right。

• 把head的左孩子和右孩子分别设置left和right，返回head，过程结束。

你肯定一脸懵逼

看看例子
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。

• 首先，根节点 是{ 1 }；
  左子树是：前序{ 2,4,7 }，中序{ 4,7,2 }；
  右子树是：前序{ 3,5,6,8 } ，中序{ 5,3,8,6 }；

• 这时，如果我们把左子树和右子树分别作为新的二叉树(即左子树是：前序{ 2,4,7 }，中序{ 4,7,2 }看成新的需要重构的二叉树)，一直递归，则可以求出其根节点，左子树和右子树。

• 这样，一直用这个方式，就可以实现重建二叉树。

假设有如下图二叉树

肉眼可得它的
前序:1,2,4,7,3,5,6,8
中序:4,7,2,1,5,3,8,6
后序:7,4,2,5,8,6,3,1
核心测试代码

      //主功能函数重构二叉树 根据前中序 返回根节点
        public static TreeNode CreateTreeByPreAndIn(int [] pre,int [] in) {
            if(pre == null || in == null){
                return null;
            }
            TreeNode root = PreAndIn(pre, in, 0, pre.length-1, 0, in.length-1);
            return root;
        }
      //核心递归
        public static TreeNode PreAndIn(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
            TreeNode tree = new TreeNode(pre[preStart]);
            if (preStart == preEnd && inStart == inEnd) {
                return tree;
            }
            int root = 0;//root表示根节点在中序的位置
            //找到前序的第一个元素(即根元素)在中序的位置
            for(root= inStart; root <= inEnd; root++){
                if (pre[preStart] == in[root]) {
                    break;
                }
            }
            //左子树的长度
            int leftLength = root - inStart;
            //右子树的长度
            int rightLength = inEnd - root;
            if (leftLength > 0) {
                tree.setLefTreeNode(PreAndIn(pre, in, preStart+1, preStart+leftLength, inStart, root-1));
            }
            if (rightLength > 0) {
                tree.setRightNode(PreAndIn(pre, in, preStart+1+leftLength, preEnd, root+1, inEnd));
            }
            return tree;
        }

已知中序和后序一样思路

只不过后序是根节点在最后
例如输入后序遍历序列{7,4,2,5,8,6,3,1}和中序遍历序列{4,7,2,1,5,3,8,6}。

• 首先，根节点 是{ 1 }；
  左子树是：后序{ 7,4,2 }，中序{ 4,7,2 }；
  右子树是：后序{ 5,8,6,3 } ，中序{ 5,3,8,6 }；
  核心测试代码

 
        //主功能函数重构二叉树 根据中后序 返回根节点
        public static TreeNode CreateTreeByPrInAndEnd(int [] end,int [] in) {
            if(end == null || in == null){
                return null;
            }
            TreeNode root = EndAndIn(end, in, 0, end.length-1, 0, in.length-1);
            return root;
        }
        
      //核心递归
        public static TreeNode EndAndIn(int[] end, int[] in, int endStart, int endEnd, int inStart, int inEnd) {
            TreeNode tree = new TreeNode(end[endEnd]);
          
            if (endStart == endEnd && inStart == inEnd) {
                return tree;
            }
            int root = 0;//root表示根节点在中序的位置
            //找到前序的第一个元素(即根元素)在中序的位置
            for(root= inStart; root <= inEnd; root++){
                if (end[endEnd] == in[root]) {
                    break;
                }
            }
            //左子树的长度
            int leftLength = root - inStart;
            //右子树的长度
            int rightLength = inEnd - root;
            System.out.println(leftLength+" wg "+rightLength);
            
            if (leftLength > 0) {
                tree.setLefTreeNode(EndAndIn(end, in, endStart, endStart+leftLength-1, inStart, root-1));
            }
            if (rightLength > 0) {
                tree.setRightNode(EndAndIn(end, in, endStart+leftLength, endEnd-1, root+1, inEnd)); 
            }
            return tree;
        }

懵逼学习，有错欢迎指正！Thanks

文章参考:https://juejin.im/post/5ab5a01d518825555c1d9a24#heading-8