java实现二叉树（一文带你详细了解二叉树的）

🎇🎇🎇作者：
@小鱼不会骑车
🎆🎆🎆专栏：
《数据结构》
🎓🎓🎓个人简介：
一名专科大一在读的小比特，努力学习编程是我唯一的出路😎😎😎

1. 树的定义

对于树，在我们现实生活中是非常常见的，大家可以看到，一个树由一个根部和很多树杈组成，就像这样：

那我们便可以根据这颗树联想到一种数据结构，就是树型结构，把它叫做树是因为它看
起来像一棵倒挂的树，也就是说它 是根朝上，而叶朝下的。

关于树的结构有很多种，但是我们现在主要学习的就是二叉树，对于AVL树，红黑树，B树，B+树，B*树……这些我们需要到高阶数据结构中才会了解到。

1.1 树的概念

1.1.1 概念

树（Tree）：

• 树是n（n >= 0）个结点的有限集。n=0 时称为空树.

• 在任意一颗非空树中有且仅有一个特定的称为根（Root）的结点，并且根节点没有前驱结点.

• 当 n>1 时，其余节点可以分为m (m>0)个互不相交的有限集T1,T2……，Tn,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）.

那我们再看看这是不是一颗树？

这种不是树，因为前面讲到过，子树之间不能有交集，切记！！！

那我们在生活中都哪里用到了树形结构呢？

举例：

就像在文件夹中，我单开一个之后出现一堆文件，点开一个又是一堆文件，其实这里涉及到的结构就是树形结构。

1.1.2 概念（重要）

这里我们结合上述图片讲解(观看顺序：上文字，下图)

• 结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为3
  

• 树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为3

• 叶子结点或终端结点：度为0的结点称为叶结点； 如上图：J,F,K,L,I节点为叶结点

• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

• 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

• 根结点：一棵树中，没有双亲结点的结点；如上图：A

• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

• 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

---

树的以下概念只需了解，在看书时只要知道是什么意思即可：

• 非终端结点或分支结点：度不为0的结点； 如上图：D、E、H、G…等节点为分支结点
• 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：G、H、I互为堂兄弟结点
• 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
• 森林：由m（m>=0）棵互不相交的树组成的集合称为森林

另外强调两点重要的：

• n>0 时根节点时唯一的，不可能存在多个根节点，别和现实中的大叔混在一起，现实中的树有很多根须，那是真正的树，数据结构中的树只能有一个跟结点。
• m>0 时，子树的个数没有限制，但是他们一定是互不相交的，如上图1-2中的结构就不符合树的定义，因为他的子树相交了.

1.2 树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
}

2. 二叉树

2.1 二叉树定义

我们做个小游戏：

猜数字：我用计算机随机一个数字，数字范围为是1~100，每猜一个数字我就会告诉你猜 “大了” 或者猜“小了”，请大家想办法猜出这个数字，有一个前提条件是猜数字的次数不能超过7次。

这个游戏对于没有接触过数据结构或者算法的人来说，他们可能猜的方法是5，10，15这样一点点的增加进行猜测，这种效率其实是很差的。

其实正确的解法应该是折半查找算法，如下图，如果用的是该算法，就一定能在七次内猜出结果（下三层省略）。

我们通过下面的代码生成0~100的随机数

   public static void main(String[] args) {Random random = new Random();Scanner scanner = new Scanner(System.in);int p = random.nextInt(100)+1;//(0包含，指定值不包含，所以+1，如果是0就变成1，如果是99就变成100)int size = 0;while (scanner.hasNextLine()) {int z = scanner.nextInt();if(z > p) {System.out.println("猜大了第"+(++size)+"次");}else if(z < p){System.out.println("猜小了第"+(++size)+"次");}else {System.out.println("第"+(++size)+"猜对了");break;}}}

下面开始测试：

如果我们用这种方式进行查找，效率会提高很多，我们可以想想，如果有100亿个数字，需要找到指定值，我们需要猜多少次？一百亿是10个0，我们按照2^10 = 1024 ,那么需要3个1024相乘再*10，我们向上取整，2 ^ 3 =8,2 ^ 4 = 16（16 > 10）,我们取4，可以得出100亿约等于2 ^ 34,那么按照每次查找一半，只需呀log(2 ^ 34)次（默认以2为底）= 34,多么恐怖啊，100亿个数字中查找一个数只需呀34次！

并且不止是折半查找，对于这种某个阶段的结果都是两种形式的，比如开和关，0和1，真和假，上和下，对与错，正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。

二叉树（Binary Tree）是 n ( n>=0 )个结点的有限集和，该集合或者为空集( 称为空二叉树 ),或者由一个根节点或两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

上图1-1的A结点有三个子树，所以不是二叉树。

2.2 二叉树的特点

2.2.1 二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是必须有子树，而是最多有。该节点没有子树或者只有一颗子树也都是可以的。
• 左子树和右子树是有顺序的，次序不能颠倒，就像我们穿鞋，如果左脚穿右鞋或者右脚穿左鞋那就会及其别扭和难受的。
• 即使树中某个结点只有一棵子树，也要区分它是左子树还是右子树，下图中，即使树1 和 树2 中存的值是一样的，但是由于结构不一样，所以他们不能称为完全相同的二叉树，就像你在班级里，你有一个同桌，那么你的同桌坐在你的左边和坐在你的右边是两种完全不一样的位序。即使人没有变，但是所处的位置是有区别的。

2.2.2 二叉树的五种基本形态

1. 空二叉树。

2. 只有一个根节点。

3. 根节点只有左树。

4. 根节点只有右树。

5. 根节点既有左树又有右树。

其实这五种形态的二叉树大家还是很容易理解的，那么我们深入探讨一下，假如有三个结点的二叉树，会有几种组合方式？

我们看下图，如果只是按照形态划分的话，那么只有三种形态，分别图1，图2，图5，如果是按照结构划分的话，那就是五种，如下图，图 1 到 图 5 分别代表着不同的二叉树。

2.3 两种特殊的二叉树

2.3.1 满二叉树

满二叉树特点:

• 在一个二叉树种，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
• 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。

2.3.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质（由公式推导附加几道练习题）

1.若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2 ^ (i-1) (i>0) 个结点.

论证：

2.若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2 ^ k - 1 (k>=0)

论证：

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

论证：
求这个结论时,我们先了解一个知识点就是一个N个节点的树有N-1条边，有了这个知识点之后，我们再进行计算：

4.具有n个结点的完全二叉树的深度k为 log(n + 1)向上取整(默认以2为底，这里忽略不写)

论证：
5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i
的结点有：

• 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
• 若2i+1<n，左孩子序号：2i+1，否则无左孩子
• 若2i+2<n，右孩子序号：2i+2，否则无右孩子

举例：

1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

3.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

答案：

1.B
解析：度为0的结点比度为2的结点多一个，题意说了度为2的结点有199，则度为0的结点为199+1=200

2.A
解析：在有2N个结点的完全二叉树，由于是完全二叉树中，那么只可能存在一个1个度为1的结点，下面就是判断度为1的结点是否存在
我们设总共有N个结点，假设度为1的结点为0
N = n0+n1+n2
N = n0+0+n2 (注：n2=n0-1)
N = 2n0-1（奇数）
所以度为1的结点为0不符合条件
接下来假设度为1的结点有1个
N = n0+n1+n2
N = n0+1+n2
N = 2n0-1+1
N =2n0(偶数，符合条件)
接下来把N替换成题意中的2N,
2N = 2n0
N = n0
最后选A

3.B
该题解法和上述一样，判断是否存在度为1的结点
由于该树是完全二叉树，并且该树的结点为767是奇数，所以可以推出度为1的结点不存在，
所以根据公式：
N = n0+n1+n2
767 = n0+0+n2
767 = 2n0-1
768 = 2n0
384 = n0

4.B
解析：有结点数求高度直接套公式：
log(531+1)向上取整 = 10，
选择B

2.5 二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}

我们重点讲解孩子表示法，结构如图

2.6 二叉树的遍历

为了后续方便讲解，我们先创建一个二叉树。

public class BinaryTree<E extends Comparable<E>> {static class Node <E>{Node<E> left;Node<E> right;E val;public Node(E val) {this.val = val;}}public Node<E> root//每个二叉树都需要一个根节点;
}

    public static void main(String[] args) {BinaryTree<Character> b = new BinaryTree<>();BinaryTree.Node<Character> A = new BinaryTree.Node<>('A');BinaryTree.Node<Character> B = new BinaryTree.Node<>('B');BinaryTree.Node<Character> C = new BinaryTree.Node<>('C');BinaryTree.Node<Character> D = new BinaryTree.Node<>('D');BinaryTree.Node<Character> E = new BinaryTree.Node<>('E');BinaryTree.Node<Character> F = new BinaryTree.Node<>('F');BinaryTree.Node<Character> G = new BinaryTree.Node<>('G');BinaryTree.Node<Character> H = new BinaryTree.Node<>('H');b.root = A;A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;}

学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

2.6.1 前序遍历

所谓前序遍历就是：根节点-》左子树-》右子树
规则是若二叉树为空，则直接返回，否则先访问根节点，然后遍历左子树，再前序遍历右子树。如下图：

我们通过代码实现以下，并且看一下结果：

    // 前序遍历void preOrder(Node <E> root){if(root==null) {return;}System.out.print(root.val+" ");preOrder(root.left);preOrder(root.right);}

运行结果：

2.6.2 中序遍历

中序遍历 左树-》根-》右树
规则：把左树遍历完了之后再去打印根节点，之后再遍历右树，遇到空就返回，否则一直递归下去。

下面就不画动图了（偷个懒哈），我们根据递归的代码带大家一步一步分析（因为需要全部放在同一个图片内，辛苦大家放大观看）：

运行结果：

代码如下：

    // 中序遍历void inOrder(Node<E>root){if(root==null) {return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}

2.6.3 后续遍历

后续遍历：左树-》右树-》根

遍历规则：先遍历左树，左树为空遍历右树，左右为空就打印

如果我们对上述的递归代码熟悉之后，那么我们便可以自己写出后序遍历的递归代码，就是调整一下打印的位置。

    // 后序遍历void postOrder(Node <E> root){if(root==null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+" ");}

2.6.4 层序遍历

关于层序遍历，我们先知道打印的顺序就好，后续会讲解

先将代码放入这里，大家可以看看：

//层序遍历void levelOrder(Node<E> root){//利用队列Queue<Node<E>> queue=new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {Node<E> cur=queue.poll();System.out.print(cur.val+"");if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);}System.out.println();}

2.6.5 前中后遍历的练习题

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为()
A: E B: F C: G D: H

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF

【参考答案】 1.A 2.A 3.D 4.A

1
1
1

2.7 二叉树的基本操作

2.7.1 获取二叉树结点个数

关于求二叉树的结点个数，我们有两种解法：

子问题思路：
子问题思路就是，将这个树分为根节点和左子树的结点数+右子树的结点数，其中每颗左子树或者右子树又是一个独立的二叉树，再次进行根节点+左子树结点+右子树结点。这里采用从左往右的遍历思路都可以（这里就不画图了，大家可以自己画图思索一下，对于数据结构多画，多想，多写代码是学好数据结构最好的利刃）

    //获取树中结点的个数public int size(Node<E> root) {if(root == null) {return 0;}return 1+size(root.left)+size(root.right);}

遍历思路：
遍历思路就是每遍历一个结点就size++,我们采取前序遍历方法（中序，后序都可以，因为每个结点只遍历了一次），遇见根节点就++

    // 获取树中节点的个数private  int size;// 获取树中节点的个数public void sizePlus(Node<E> root) {if(root==null) {return ;}size++;sizePlus(root.left);sizePlus(root.right);}

2.7.2 获取叶子节点个数

2.7.2.1 遍历思路

所谓叶子节点就是度为0的结点，就说明叶子节点是没有左子树和右子树的，那么我们的代码就可以把判断条件改为，只要是该节点的左树和右树为空，那就count++,代码入下:

    // 获取叶子节点的个数,遍历思路//遍历思路，求得叶子个数然后再去调用leaf就可以得到叶子的个数//叶子个数int count = 0;public int getLeafNodeCountPlus(Node<E> root){funcGetLeafNodeCountPlus(root);return count;}public void funcGetLeafNodeCountPlus(Node<E> root) {if(root==null) {return ;}//左子树右子树为空就++if(root.left==null&&root.right==null) {count++;}funcGetLeafNodeCountPlus(root.left);funcGetLeafNodeCountPlus(root.right);}

2.7.2.2 子问题思路

子问题思路就是，左子树的叶子结点+右树的叶子结点，每个左子树或者右子树又是一个新的二叉树.

    // 子问题思路-求叶子结点个数public int funcGetLeafNodeCountPlus(Node<E> root) {if(root == null) {return 0;}//左右树为空就返回1if(root.left == null && root.right == null) {return 1;}return funcGetLeafNodeCountPlus(root.left)+funcGetLeafNodeCountPlus(root.right);}

2.7.3 获取第K层结点的个数

所谓获取第K层的结点个数，那么我们可以定义一个记录高度的变量，当我的高度和k相同，并且该节点不为空，那就说明这个结点是第k层的结点。

2.7.3.1 遍历思路

如果是第k层结点就count++

 /*** 左树的第n层和右树的第n层* 遍历* @param root k* @return int*/public int count;int getKLevelNodeCount(Node<E> root,int k){funcGetKLevelNodeCount(root,k);return count;}public void funcGetKLevelNodeCount (Node<E> root,int k) {if(k==1&&root!=null) {count++;return;}if(root==null) {return;}getKLevelNodeCount(root.left,k-1);getKLevelNodeCount(root.right,k-1);}

2.7.3.2 子问题思路

左子树的第k层结点+右子树的第k层结点。

   /*** 子问题解决求树的第n层的结点* @param root k* @return int*/int getKLevelNodeCountPlus(Node<E> root,int k){if(root==null) {return 0;}if(k==1) {return 1;}//左树第k层结点+右树第k层结点return getKLevelNodeCountPlus(root.left,k-1)+ getKLevelNodeCountPlus(root.right,k-1);}

2.7.4 获取二叉树的高度

获取二叉树的高度这道题，上述讲到了（树的高度或深度：树中结点的最大层次）因为要找到树的最大层次，所以第一件事就是找到叶子结点然后开始返回，但是并不是所有的叶子节点都在最后一层（如图1），所以我们可以思考一下，可不可以将获取树的高度这个问题分解一下，改成获取左子树的高度和右子树的高度，然后对比哪个高，就返回哪个并且加上根节点，因为根节点本身也占一层。那调用左子树的高度时，又变成了获取该树的左子树和右子树深度的最大值再加上当前的根节点。那么我们可以根据这个思路去写代码：

    // 获取二叉树的高度/*** 比较左树和右树的高度* @param root* @return*/public int getHeight(Node<E> root){if(root==null) {return 0;}int a=getHeight(root.left);int b=getHeight(root.right);//左树高度和右树高度求最大值再+1return Math.max(a+1, b+1);}

2.7.5 检测value的元素是否存在

采用遍历思路，当根节点的值为 val 时就返回 true ,如果根节点为空说明没有找到就返回 false ,如果根节点不为null，并且还没有找到val，那么继续去左树和右树中查找，如果找到了就返回true,最后的返回值是左子树| | 右子树，只要有一个为真就返回真！

    // 检测值为value的元素是否存在public boolean find(Node<E> root, E val){if(root==null) {return false;}if(root.val==val) {return true;}//遍历当前结点和左子树和右子树boolean a1= find(root.left,val);boolean a2 = find(root.right,val);return a1||a2;}

2.7.6 层序遍历

层序遍历上述也介绍到了，就是从左到右，从上到下遍历，遍历完这一层所有的结点，再去遍历下一层的结点。

对于层序遍历我们需要借助一个工具，就是队列，我们来看图：

代码如下：

    //层序遍历void levelOrder(Node<E> root){//利用队列Queue<Node<E>> queue=new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {Node<E> cur=queue.poll();System.out.print(cur.val+"");if(cur.left!=null)queue.offer(cur.left);if(cur.right!=null)queue.offer(cur.right);}System.out.println();}

2.7.7 判断一颗树是不是完全二叉树

关于完全二叉树的介绍上述有讲到，判断完全二叉树也是需要一个工具，依旧是队列，上述的队列实现了层序遍历，那么我们可以在这个层序遍历的基础上给升级一下，我们通过完全二叉树和非完全二叉树来对比一下：

完全二叉树：

非完全二叉树：

根据对比我们发现，完全二叉树的队列，当出第一个空结点后，其余结点都是空结点，但是非完全二叉树的队列，在弹出第一个空结点后，其余结点一定有非空结点。
代码入下：

// 判断一棵树是不是完全二叉树boolean isCompleteTree(Node<E> root){//队列实现Deque<Node<E>> queue=new LinkedList<>();queue.offer(root);//为空退出循环while (queue.peek()!=null){Node<E> cur=queue.poll();queue.offer(cur.left);queue.offer(cur.right);}//判断剩余结点是否包含非空节点for (int i = 0; i < queue.size(); i++) {if(queue.poll()!=null) {return false;}}return true;}