【全面解析！】二叉树及其应用_二叉树的应用场景及流程

二叉树的基本概念

树形结构

树形结构中包含根结点和子结点，根结点就是没有前驱的结点；
子结点之间不能有交集，不能相交，否则不构成树形结构；
除了根结点之外其他结点有且仅有一个父结点；
一棵N个结点的树有N-1条边；

树的深度和高度：树的高度针对的是整体而言，所以该图中高度为4；而深度是针对单个结点而言，就像B深度是2

在写代码的时候我们知道，一棵树的高度其实就是这棵树的最大深度

二叉树

二叉树的基本概念

注意：二叉树与树形结构的区分

1.二叉树不存在度大于2的结点
2.二叉树是有序的，不是大小的有序，是顺序有序，因为它有左右子树之分；每个结点都是有左右之分的

特殊的二叉树

1.满二叉树：即每一层都放满，假如有二叉树有k层，则结点总数是（2的k次方）-1

2.完全二叉树：满二叉树是一种特殊的完全二叉树

二叉树的性质

1.若规定根结点的层数为1，那么一棵非空二叉树的第i层最多有2的（i-1)次方个结点【就是每个结点都存在左右两个孩子即为最多】
2.若规定只有二叉树的根结点的深度为1，则深度为k的二叉树的最大结点数是（2的k次方）-1

3.对于任意一棵二叉树，叶子结点的个数永远比度为2的结点个数多1
书面表达：对于任意一个二叉树，如果其叶结点的个数为n0，度为2的非叶结点的个数 为n2，则有n0=n2+1
4.
4.1n个结点的完全二叉树的深度为：
4.2

5.父亲结点和子结点相互计算 根节点从0开始编号使用这个公式
后期在学习堆的时候经常使用这个公式
（1）已知父亲结点i，则孩子结点为：
左孩子：(2i)+1；右孩子：（2i）+2
（2）已知孩子结点为i，则父亲结点为**（i-1）/2**
题目练习：

二叉树的存储

（1）前序遍历：根左右—遇到根结点就打印；得到顺序为：ABDCEF

（2）中序遍历：左根右；得到顺序为：DBAECF
（每一个子树都要保证它的遍历方式为左根右，彻底完成才能进行下一个)

（3）后序遍历：左右根；得到顺序为：DBEFCA；**
（每一个子树都要保证它的遍历方式为左根右，彻底完成才能进行下一个，即必须把左右走完才能打印根)**
（4）层序遍历：按顺序从上到下，从左到右；得到顺序为：ABCDEF

做题技巧

练习1：

**练习2：**后序遍历的最后一个元素是根结点，因为左右根；后序的倒数第二个元素在中序中划分左右子树，与上面相同

注意：我们根据前序遍历顺序和后序遍历顺序并不能创造出一个二叉树，因为这两个都只能提供根结点元素，无法知道元素之间的具体位置，所以我们要创建出一个二叉树必须要一个中序遍历的顺序

二叉树存储代码

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode right;
        public  TreeNode left;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
    TreeNode A=new TreeNode('A');
    TreeNode B=new TreeNode('B');
    TreeNode C=new TreeNode('C');
    TreeNode D=new TreeNode('D');
    TreeNode E=new TreeNode('E');
    TreeNode F=new TreeNode('F');
    TreeNode G=new TreeNode('G');
    TreeNode H=new TreeNode('h');
    A.left=B;
    A.right=C;
    B.left=D;
    B.right=E;
    C.left=F;
    C.right=G;
    e.right=H;
    return A;
    }
    public void preOrder(TreeNode root){
        if(root==null) return;
        System.out.println(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        System.out.println(root.val+" ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if(root==null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val+" ");
    }
    public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> ret=new ArrayList<>();
        if(root==null) return ret;
        ret.add(root);
        List<TreeNode> leftTree= preOrder2(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree=preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        BinaryTree.TreeNode root=binaryTree.createTree();
        System.out.println("========");

     /*   binaryTree.preOrder(root);
        System.out.println();*/
        binaryTree.preOrder2(root);
        System.out.println();

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

二叉树的基本操作

  //获取树中结点的个数-方法1
    public int size(TreeNode root) {
        if (root == null) return 0;
        int leftSize = size(root.left);
        int rightSize = size(root.right);
        int Size = leftSize + rightSize + 1;
        return Size;
    }

    //获取树中结点的个数-方法2
    int Size2 = 0;

    public int size2(TreeNode root) {
        if (root == null) return 0;
        size2(root.left);
        Size2++;//左右子树回去过去只计一次数就好
        size2(root.right);
        return Size2;
    }

    //求叶子结点的个数
    int sizeLeaf = 0;

    public int getLeafNodeCount(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            sizeLeaf++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return sizeLeaf;
    }

    //获取第k层结点的个数
    //解题思路：不是直接求第K层的结点个数，
    // 而是往下移动一层，看root.left/root.right的k-1层
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return (getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1));
    }

    //获取二叉树的高度，即二叉树的最大深度就是该树的高度
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftTree = getHeight(root.left);
        int rightTree = getHeight(root.right);
        return (leftTree > rightTree ? leftTree + 1 : rightTree + 1);
       
    }
//检测值为value的元素是否存在
    public boolean find(TreeNode root,int key){
        if(root==null) return false;
        if(root.val==key) return  true;
        boolean leftTree=find(root.left,key);
        if(leftTree==true){//因为find方法返回值类型为boolean，所以我们这样表示递归
            return true;
        }
        boolean rightTree=find(root.right,key);
        if(rightTree==true){
            return true;
        }
        return false;
    }
    //层序遍历--普通层序遍历不需要使用递归方法，
// 也不用构建顺序表，链表去存放它的元素，直接出入队列即可实现
     public void levelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null) return;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
           if(cur.left!=null){
               queue.offer(cur.left);
           }
           if(cur.right!=null){
               queue.offer(cur.right);
           }
        }
    }
    //判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root){
       if(root==null) {
           return true;
       }
       Queue<TreeNode> queue=new LinkedList<>();
       TreeNode cur;
       queue.offer(root);
       while(!queue.isEmpty()){
           cur=queue.poll();
           if(cur!=null){
               queue.offer(cur.left);//如果cur为叶子结点，那么队列中加入两个null，在执行下次循环的时候新的cur就被赋值为null，然后跳出第一个while循环
               queue.offer(cur.right);
           }else{
               break;
           }
       }
       while(!queue.isEmpty()){
           cur=queue.poll();
           if(cur!=null){
               return false;
           }
       }
       return true;
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

二叉树易错总结

1.在用树表示的目录结构中，从根目录到任何数据文件只有唯一一条通道，因为树的特点是不相交
2.

3.（1）根据中序遍历和后序遍历顺序构建二叉树
（2）根据前序遍历和中序遍历顺序构建二叉树
Q1：为什么后序+中序构建二叉树是先root.left再root.right;而前序+中序构建二叉树是先root.right再root.left?
A1:
根据上面的图片我们可以看到，根据后序遍历的顺序，我们先在中序中找到根节点，下一步找到的是右树，所以我们在写代码的时候要先写root，再right，最后left；前序+中序遍历构建同理，是先root，再left，最后构建二叉树的right

递归方法使用注意：
递归方法每return回去一次，它方法中所包含的变量就会被销毁掉，所以，如果我们不想该变量随着递归方法return返回而被销毁掉的话，我们一般将变量设置为成员变量（置于递归方法之外）而非局部变量（在递归方法之中）PS：【1】像这两道题中的preIndex和postIndex这两个变量的设置【2】这两道题中的begin和end也不是一直不变的！它随着方法的递归而改变，也随着递归方法的return而被销毁掉，返回上一级方法的begin和end值！！