Java数据结构——二叉树（Binary Tree）详解

学数据结构的时候，二叉树算是一个非常重要的内容。前面的顺序表、链表、栈、队列，本质上都属于线性结构，数据之间基本是一对一的关系。

而二叉树就不一样了，它是一种典型的树形结构。一个节点下面可以继续连接子节点，数据之间不再是简单的前后关系，而是具有明显的层次关系。

这篇文章主要把二叉树的基础概念、常见性质、存储方式以及几种遍历方式过一遍，先把地基打稳。后面像堆、二叉搜索树、二叉树相关 OJ 题，都可以在这个基础上继续展开。

一、树形结构

在了解二叉树之前，首先需要知道什么是树。

树是一种非线性的数据结构，它是由若干个节点组成的集合。树中有一个特殊节点，称为根节点，其余节点可以看成根节点下面的子树。

简单来说，树形结构就像下面这样：

A / | \ B C D / \ E F

在这个结构中，A 是根节点，B、C、D 是 A 的孩子节点，E、F 又是 C 的孩子节点。

树的表示方式有很多种，常见的有以下几种：

在 Java 中，我们最常见的写法就是链式表示法。

二、二叉树是什么？

二叉树是一种特殊的树形结构，它的特点是：每个节点最多只有两个孩子节点。

这两个孩子节点通常被称为：

• 左孩子
• 右孩子

对应的，以某个节点的左孩子为根的树，称为左子树；以右孩子为根的树，称为右子树。

例如下面这棵树就是一棵二叉树：

A / \ B C / \ \ D E F

可以看出，每个节点最多只有两个孩子节点。

需要注意的是，二叉树不是要求每个节点都必须有两个孩子，而是最多有两个孩子。

例如下面这些情况都是二叉树：

只有左孩子： A / B 只有右孩子： A \ C 空树： null

空树也可以看作是一棵二叉树，这一点在后面写递归代码的时候非常重要。

三、二叉树中的基础概念

3.1 节点的度

一个节点含有的子树个数，称为该节点的度。

在二叉树中，一个节点的度只可能有三种情况：

• 度为 0：没有孩子节点
• 度为 1：只有一个孩子节点
• 度为 2：有两个孩子节点

例如：

A / \ B C / D

在这棵树中：

• A 有两个孩子，所以 A 的度为 2
• B 有一个孩子，所以 B 的度为 1
• C 和 D 没有孩子，所以它们的度为 0

3.2 树的度

一棵树中，所有节点的度的最大值，称为树的度。

二叉树中每个节点最多只有两个孩子，所以二叉树的度最大为 2。

3.3 叶子节点

度为 0 的节点称为叶子节点，也叫终端节点。

简单来说，就是没有孩子节点的节点。

A / \ B C / \ D E

在这棵树中，C、D、E 都是叶子节点。

3.4 父节点和孩子节点

如果一个节点下面连接了其他节点，那么这个节点就是这些节点的父节点。

反过来，被连接的节点就是它的孩子节点。

例如：

A / \ B C

A 是 B 和 C 的父节点，B 和 C 是 A 的孩子节点。

3.5 根节点

一棵树中，没有父节点的节点称为根节点。

一棵非空树有且只有一个根节点。

3.6 节点的层次

节点的层次一般从根节点开始计算。

如果规定根节点是第一层，那么根节点的孩子就是第二层，依次往下。

第1层： A / \ 第2层： B C / \ 第3层： D E

3.7 树的高度或深度

树中节点的最大层次，称为树的高度或深度。

上面的树一共有 3 层，所以它的高度就是 3。

四、二叉树的几个重要性质

二叉树有一些非常常用的性质，后面在堆、完全二叉树、二叉树题目中都会反复用到。

4.1 第 i 层最多有多少个节点？

如果规定根节点在第 1 层，那么一棵非空二叉树的第 i 层最多有：

2^(i - 1)

个节点。

例如：

可以看出，每往下一层，最多节点数都会变成上一层的 2 倍。

4.2 深度为 K 的二叉树最多有多少个节点？

如果规定只有根节点的二叉树深度为 1，那么深度为 K 的二叉树最多有：

2^K - 1

个节点。

例如深度为 3 的二叉树最多有：

2^3 - 1 = 7

个节点。

图示如下：

A / \ B C / \ / \ D E F G

这里一共有 7 个节点。

需要注意的是，性质 1 和性质 2 很容易混淆。

• 性质 1 回答的是：某一层最多有几个节点？
• 性质 2 回答的是：整棵树最多有几个节点？

一个是局部，一个是整体。

4.3 叶子节点数和度为 2 的节点数关系

对任意一棵二叉树，如果叶子节点个数为n0，度为 2 的节点个数为n2，那么有：

n0 = n2 + 1

这个结论很常用，但是刚开始看可能会觉得有点奇怪。

接下来简单推导一下。

假设：

n0 表示度为 0 的节点个数 n1 表示度为 1 的节点个数 n2 表示度为 2 的节点个数 N 表示总节点个数

那么整棵树的节点总数为：

N = n0 + n1 + n2

又因为一棵有 N 个节点的树，一定有 N - 1 条边。

每个度为 1 的节点会贡献 1 条向下的边，每个度为 2 的节点会贡献 2 条向下的边，所以边的数量又可以表示为：

n1 + 2 * n2 = N - 1

将N = n0 + n1 + n2代入：

n1 + 2 * n2 = n0 + n1 + n2 - 1

两边同时消去n1：

2 * n2 = n0 + n2 - 1

两边同时减去n2：

n2 = n0 - 1

所以：

n0 = n2 + 1

简单来说，二叉树中叶子节点的数量，总是比度为 2 的节点数量多 1。

4.4 完全二叉树的深度

如果一棵完全二叉树有 n 个节点，那么它的深度 K 可以表示为：

K = 向上取整 log2(n + 1)

也可以理解为：

K = 向下取整 log2(n) + 1

例如有 6 个节点的完全二叉树：

A / \ B C / \ / D E F

它的深度就是 3。

五、完全二叉树的下标关系

完全二叉树有一个很重要的特点：它非常适合用数组来存储。

假设一棵完全二叉树从上到下、从左到右依次编号，并且从 0 开始编号：

下标： 0 / \ 1 2 / \ / \ 3 4 5 6

如果当前节点下标为i，总节点个数为n，那么：

需要注意：

• 如果2 * i + 1 >= n，说明当前节点没有左孩子
• 如果2 * i + 2 >= n，说明当前节点没有右孩子
• 根节点的下标为 0，它没有父节点

这个性质后面在堆中非常重要。

因为堆的底层就是数组，而堆本质上是在完全二叉树的基础上加了一些规则。

六、二叉树的存储方式

二叉树常见的存储方式有两种：

• 顺序存储
• 链式存储

6.1 顺序存储

顺序存储就是使用数组来存储二叉树。

但是需要注意：顺序存储比较适合完全二叉树，不太适合普通二叉树。

例如完全二叉树：

A / \ B C / \ / D E F

可以按照层序放入数组：

[A, B, C, D, E, F]

因为完全二叉树从上到下、从左到右基本是连续的，所以数组中不会浪费太多空间。

但是如果是下面这种树：

A \ B \ C

如果仍然按照完全二叉树的下标规则存储，就会出现很多空位置。

所以普通二叉树通常不建议用顺序结构进行存储。

6.2 链式存储

链式存储是二叉树最常见的存储方式。

每个节点除了保存自己的值，还保存左孩子和右孩子的引用。

classTreeNode{intval;TreeNodeleft;TreeNoderight;publicTreeNode(intval){this.val=val;}}

其中：

• val表示当前节点存储的数据
• left指向当前节点的左孩子
• right指向当前节点的右孩子

如果还需要快速找到父节点，也可以增加一个parent引用：

classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNodeparent;publicTreeNode(intval){this.val=val;}}

不过普通二叉树题目中，最常用的还是第一种写法，也就是只保存left和right。

七、手动创建一棵二叉树

接下来创建一棵简单的二叉树，用于后面演示遍历。

目标结构如下：

1 / \ 2 3 / \ \ 4 5 6

代码如下：

publicclassBinaryTreeDemo{staticclassTreeNode{intval;TreeNodeleft;TreeNoderight;publicTreeNode(intval){this.val=val;}}publicstaticTreeNodebuildTree(){TreeNoderoot=newTreeNode(1);TreeNodenode2=newTreeNode(2);TreeNodenode3=newTreeNode(3);TreeNodenode4=newTreeNode(4);TreeNodenode5=newTreeNode(5);TreeNodenode6=newTreeNode(6);root.left=node2;root.right=node3;node2.left=node4;node2.right=node5;node3.right=node6;returnroot;}}

通过这段代码，就可以把一个个独立的节点连接成一棵二叉树。

需要注意的是，二叉树中的left和right保存的是节点引用，而不是节点的值。

也就是说，root.left = node2表示 root 的左孩子指向 node2 这个节点。

八、二叉树的遍历方式

遍历就是把二叉树中的每个节点都访问一遍。

二叉树常见的遍历方式有四种：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

前三种遍历都可以用递归来实现，区别在于根节点的访问时机不同。

简单来说，前序、中序、后序中的“前、中、后”，指的是根节点访问的位置。

8.1 前序遍历

前序遍历的顺序是：

根 -> 左 -> 右

以上面的二叉树为例：

1 / \ 2 3 / \ \ 4 5 6

前序遍历结果为：

1 2 4 5 3 6

代码实现如下：

publicstaticvoidpreorder(TreeNoderoot){if(root==null){return;}System.out.print(root.val+" ");preorder(root.left);preorder(root.right);}

结果剖析：

1. 先访问根节点 1
2. 再进入左子树，访问 2、4、5
3. 左子树访问完后，再进入右子树，访问 3、6

8.2 中序遍历

中序遍历的顺序是：

左 -> 根 -> 右

对应结果为：

4 2 5 1 3 6

代码实现如下：

publicstaticvoidinorder(TreeNoderoot){if(root==null){return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}

中序遍历有一个非常重要的应用：如果一棵树是二叉搜索树，那么它的中序遍历结果就是有序的。

这个性质后面在讲二叉搜索树时会非常常用。

8.3 后序遍历

后序遍历的顺序是：

左 -> 右 -> 根

对应结果为：

4 5 2 6 3 1

代码实现如下：

publicstaticvoidpostorder(TreeNoderoot){if(root==null){return;}postorder(root.left);postorder(root.right);System.out.print(root.val+" ");}

后序遍历的特点是：根节点最后被访问。

所以它经常适合处理“先处理左右子树，再处理当前节点”的问题。

例如：

• 求树的高度
• 判断一棵树是否平衡
• 删除或释放整棵树

8.4 层序遍历

层序遍历的顺序是从上到下、从左到右。

还是这棵树：

1 / \ 2 3 / \ \ 4 5 6

层序遍历结果为：

1 2 3 4 5 6

层序遍历通常需要借助队列来实现。

核心思路：

1. 先把根节点放入队列
2. 每次从队列中取出一个节点并访问
3. 如果该节点有左孩子，就把左孩子入队
4. 如果该节点有右孩子，就把右孩子入队
5. 重复上述过程，直到队列为空

代码实现如下：

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

为什么层序遍历要使用队列？

因为层序遍历要求先访问先遇到的节点，而队列刚好是先进先出（FIFO）的结构。

九、完整代码展示

下面给出一份完整代码，可以直接运行观察四种遍历结果。

importjava.util.LinkedList;importjava.util.Queue;publicclassBinaryTreeDemo{staticclassTreeNode{intval;TreeNodeleft;TreeNoderight;publicTreeNode(intval){this.val=val;}}publicstaticTreeNodebuildTree(){TreeNoderoot=newTreeNode(1);TreeNodenode2=newTreeNode(2);TreeNodenode3=newTreeNode(3);TreeNodenode4=newTreeNode(4);TreeNodenode5=newTreeNode(5);TreeNodenode6=newTreeNode(6);root.left=node2;root.right=node3;node2.left=node4;node2.right=node5;node3.right=node6;returnroot;}publicstaticvoidpreorder(TreeNoderoot){if(root==null){return;}System.out.print(root.val+" ");preorder(root.left);preorder(root.right);}publicstaticvoidinorder(TreeNoderoot){if(root==null){return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}publicstaticvoidpostorder(TreeNoderoot){if(root==null){return;}postorder(root.left);postorder(root.right);System.out.print(root.val+" ");}publicstaticvoidlevelOrder(TreeNoderoot){if(root==null){return;}Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecur=queue.poll();System.out.print(cur.val+" ");if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}}}publicstaticvoidmain(String[]args){TreeNoderoot=buildTree();System.out.print("前序遍历：");preorder(root);System.out.println();System.out.print("中序遍历：");inorder(root);System.out.println();System.out.print("后序遍历：");postorder(root);System.out.println();System.out.print("层序遍历：");levelOrder(root);System.out.println();}}

执行代码后，输出内容如下：

前序遍历：1 2 4 5 3 6 中序遍历：4 2 5 1 3 6 后序遍历：4 5 2 6 3 1 层序遍历：1 2 3 4 5 6

十、特殊的二叉树

二叉树中还有几种比较特殊的结构。

10.1 满二叉树

满二叉树指的是：每一层的节点数都达到最大值。

例如：

1 / \ 2 3 / \ / \ 4 5 6 7

这就是一棵满二叉树。

如果一棵满二叉树的深度为 K，那么它的节点个数一定是：

2^K - 1

10.2 完全二叉树

完全二叉树指的是：

除了最后一层之外，其他层都是满的，并且最后一层的节点从左到右连续排列。

例如：

1 / \ 2 3 / \ / 4 5 6

这是一棵完全二叉树。

但下面这个就不是完全二叉树：

1 / \ 2 3 \ \ 5 6

因为最后一层不是从左到右连续排列，中间出现了空缺。

10.3 堆

堆本质上是一棵完全二叉树。

只不过堆在完全二叉树的基础上，又增加了父子节点之间的大小关系。

常见的堆有两种：

Java 中的PriorityQueue底层就使用了堆这种数据结构。

堆的调整、建堆、插入和删除操作比较重要，后面可以单独写一篇。

10.4 二叉搜索树

二叉搜索树也是一种特殊的二叉树。

它的特点是：

• 左子树中所有节点的值都小于根节点
• 右子树中所有节点的值都大于根节点
• 左右子树也分别是二叉搜索树

直白一点：左边都比根小，右边都比根大。

二叉搜索树的查找过程和二分查找很像，每次都可以根据大小关系决定往左走还是往右走。

这个内容后面也可以单独展开。

十一、容易混淆的几个点

11.1 前序、中序、后序到底看什么？

看根节点的位置。

不要把“左”和“右”的位置记乱，三种递归遍历中，左子树一般都先于右子树访问，变化的是根节点访问的位置。

11.2 深度和高度一定一样吗？

在很多基础数据结构文章中，树的高度和深度经常混着使用，都是表示树的最大层数。

但在一些更严谨的场景中：

• 深度更偏向从根节点往下数
• 高度更偏向从叶子节点往上数

初学阶段先理解为“这棵树有多少层”即可。

11.3 空树要不要处理？

必须处理。

二叉树代码中，经常会出现：

if(root==null){return;}

这就是递归的终止条件。

如果没有这个判断，递归会一直往下访问空节点，最终出现空指针异常。

11.4 普通二叉树适合用数组存吗？

一般不适合。

数组存储适合完全二叉树，因为下标关系连续，不会浪费太多空间。

普通二叉树如果结构比较偏，比如只有右孩子，就会导致数组中出现大量空位置，空间浪费比较明显。

所以普通二叉树更常用链式存储。

十二、相关OJ题目

相关OJ题目详见：Java数据结构——二叉树相关OJ题目详解

end*