二叉树【Java】

树

什么是树结构

树作为一种一对多的数据结构，是由n（n>0）个结点组成的有限集合；n=0是一棵空数，空数也可以看做是一棵树；

树的相关概念

下面的结构就是一棵具体的树：

对于这样一棵树而言：

• 树的结点：树的每个元素称为树的一个结点，每个结点都可以作为一棵树的根来引出下一棵子树；
• 结点的度：一个结点含有的子树的个数；例如上图中，结点A的度为2，结点C的度为1；
• 树的度：一棵树中，所有结点的最大值称为树的度；上图中树的度为2；
• 叶子结点（终端结点）：一棵树中，度为0的结点称为叶子结点；上图中D、E、F都是叶子结点；
• 双亲结点（父节点）和孩子结点（子节点）：例如上图中，A是B的父节点，B和C是A的子节点；
• 根结点：一棵树中，没有双亲结点的结点为树的根结点；上图树的根节点为A；
• 结点的层次：从根结点开始为第一层，根节点的子节点为第二层，以此类推；
• 树的高度：树中结点的最大层次；上图中树的高度为3；
• 深度：深度是相对结点的，即根节点到某个结点的距离；对于整棵树来说，树的高度和深度是相等的；

树的存储结构

树的存储结构是一种不同于顺序存储和链式存储的结构，主要有下面的几种存储方式：

• 双亲表示法：用一组连续的空间来存储树的结点，为每个结点设置一个指示器来标明该结点的双亲结点；

• 孩子表示法：由于树中的结点往往不止有一个子节点，我们可以为每个结点设置多个指针域，标明该结点的孩子结点；

• 孩子兄弟表示法：为每个结点设置2个指针域，一个是该结点第一个孩子的指向，第二个是该结点的下一个兄弟结点；

其实，在实际的程序设计过程中，树的存储结构有许多种方式，而我们一般使用较多的就是孩子兄弟表示法；

二叉树

二叉树的概念

二叉树是n个结点的有限集合，该集合由一个根节点和2棵互不相交的称为根节点的左子树和右子树的二叉树组成；

几种特殊的二叉树

• 满二叉树：二叉树的所有分支结点都具有左右子树，并且所有的叶子结点都在同一层；
• 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点的位置完全相同，这就是一棵完全二叉树；

二叉树的性质

• 每个结点最多有2棵子树，因此二叉树中不存在度大于2的结点；
• 二叉树的左右子树不可以颠倒，因此二叉树是有序树；
• 设二叉树的根结点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1） (i>0)个结点；

• 设根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k-1 (k>=0)个;

• 具有n个结点的完全二叉树的深度k为 log(n+1) (底数为2)向上取整；

• 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1；

• 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
  若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点；
  若2i+1 若2i+2

二叉树的基本操作

二叉树的基本操作主要就是对通过对二叉树遍历再进行相关的操作，这里对二叉树的所有操作都基于这样一棵二叉树：

import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        public char val;    //当前结点存储的值
        public TreeNode left;       //左孩子
        public TreeNode right;      //右孩子

        public TreeNode(char val){
            this.val=val;
        }
    }
/**
 * 手动创建一棵二叉树
 * 返回二叉树的根结点
 * */
    public TreeNode CreateBinaryTree(){
        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');
        TreeNode I=new TreeNode('I');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.right=F;
        D.left=G;
        D.right=H;
        E.right=I;

        return A;

    }
/**
 * 前序遍历（根-左-右）
 * */
    void preOrder(TreeNode root){
        if (root==null){
            return ;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 中序遍历（左-根-右）
     * */
    void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    /**
     * 后序遍历（左-右-根）
     * */
    void postOrder(TreeNode root){
        if (root==null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * 层序遍历(从根结点开始，从左到右逐层遍历)
     *
     * */
    void  levelOrder(TreeNode root){

        if(root==null){
            return ;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left!=null){
                queue.offer(cur.left);
            }
           if (cur.right!=null){
               queue.offer(cur.right);
           }


        }
    }




    /**
     * 获取树中节点的个数
     * 由于递归的特殊性，计数器必须在递归函数之外，否则每次递归计数器都会置0；
     * */
    int count=0;
    int size(TreeNode root){

        if (root==null){
            return 0;
        }
        size(root.left);
        count++;
        size(root.right);
        return count;
    }


    //

    /**
     * 获取叶子节点的个数
     * 遍历二叉树，当结点的左右孩子都为空时，为叶子结点，计数器加1；
     * */
    int getLeafNodeCount(TreeNode root){
        if (root==null){
            return 0;
        }

        if (root.left==null&&root.right==null){
            count++;
        }
        getLeafNodeCount(root.left);

         getLeafNodeCount(root.right);


        return count;
    }



    /**
     *  获取第K层节点的个数
     *
     * */
    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);

    }

    /**
     * 获取二叉树的高度
     * 即左右数高度的最大值+1；
     * */
    int getHeight(TreeNode root){
        if (root==null) return 0;
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }


    /**
     * 检测值为value的元素是否存在
     *
     * */
    TreeNode find(TreeNode root, int val){
        if (root==null) return null;
        if (root.val==val) return root;
        TreeNode ret=find(root.left,val);
        if (ret!=null){
            return ret;
        }
         ret=find(root.right,val);
        if (ret!=null){
            return ret;
        }
        return null;


    }
    
   
}
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

over！