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 的度为 2B 有一个孩子所以 B 的度为 1C 和 D 没有孩子所以它们的度为 03.2 树的度一棵树中所有节点的度的最大值称为树的度。二叉树中每个节点最多只有两个孩子所以二叉树的度最大为 2。3.3 叶子节点度为 0 的节点称为叶子节点也叫终端节点。简单来说就是没有孩子节点的节点。A / \ B C / \ D E在这棵树中C、D、E 都是叶子节点。3.4 父节点和孩子节点如果一个节点下面连接了其他节点那么这个节点就是这些节点的父节点。反过来被连接的节点就是它的孩子节点。例如A / \ B CA 是 B 和 C 的父节点B 和 C 是 A 的孩子节点。3.5 根节点一棵树中没有父节点的节点称为根节点。一棵非空树有且只有一个根节点。3.6 节点的层次节点的层次一般从根节点开始计算。如果规定根节点是第一层那么根节点的孩子就是第二层依次往下。第1层 A / \ 第2层 B C / \ 第3层 D E3.7 树的高度或深度树中节点的最大层次称为树的高度或深度。上面的树一共有 3 层所以它的高度就是 3。四、二叉树的几个重要性质二叉树有一些非常常用的性质后面在堆、完全二叉树、二叉树题目中都会反复用到。4.1 第 i 层最多有多少个节点如果规定根节点在第 1 层那么一棵非空二叉树的第 i 层最多有2^(i - 1)个节点。例如层数最多节点数第 1 层1第 2 层2第 3 层4第 4 层8可以看出每往下一层最多节点数都会变成上一层的 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两边同时消去n12 * n2 n0 n2 - 1两边同时减去n2n2 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那么目标节点下标公式父节点(i - 1) / 2左孩子2 * i 1右孩子2 * i 2需要注意如果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.valval;}}其中val表示当前节点存储的数据left指向当前节点的左孩子right指向当前节点的右孩子如果还需要快速找到父节点也可以增加一个parent引用classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNodeparent;publicTreeNode(intval){this.valval;}}不过普通二叉树题目中最常用的还是第一种写法也就是只保存left和right。七、手动创建一棵二叉树接下来创建一棵简单的二叉树用于后面演示遍历。目标结构如下1 / \ 2 3 / \ \ 4 5 6代码如下publicclassBinaryTreeDemo{staticclassTreeNode{intval;TreeNodeleft;TreeNoderight;publicTreeNode(intval){this.valval;}}publicstaticTreeNodebuildTree(){TreeNoderootnewTreeNode(1);TreeNodenode2newTreeNode(2);TreeNodenode3newTreeNode(3);TreeNodenode4newTreeNode(4);TreeNodenode5newTreeNode(5);TreeNodenode6newTreeNode(6);root.leftnode2;root.rightnode3;node2.leftnode4;node2.rightnode5;node3.rightnode6;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(rootnull){return;}System.out.print(root.val );preorder(root.left);preorder(root.right);}结果剖析先访问根节点 1再进入左子树访问 2、4、5左子树访问完后再进入右子树访问 3、68.2 中序遍历中序遍历的顺序是左 - 根 - 右对应结果为4 2 5 1 3 6代码实现如下publicstaticvoidinorder(TreeNoderoot){if(rootnull){return;}inorder(root.left);System.out.print(root.val );inorder(root.right);}中序遍历有一个非常重要的应用如果一棵树是二叉搜索树那么它的中序遍历结果就是有序的。这个性质后面在讲二叉搜索树时会非常常用。8.3 后序遍历后序遍历的顺序是左 - 右 - 根对应结果为4 5 2 6 3 1代码实现如下publicstaticvoidpostorder(TreeNoderoot){if(rootnull){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层序遍历通常需要借助队列来实现。核心思路先把根节点放入队列每次从队列中取出一个节点并访问如果该节点有左孩子就把左孩子入队如果该节点有右孩子就把右孩子入队重复上述过程直到队列为空代码实现如下importjava.util.LinkedList;importjava.util.Queue;publicstaticvoidlevelOrder(TreeNoderoot){if(rootnull){return;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.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.valval;}}publicstaticTreeNodebuildTree(){TreeNoderootnewTreeNode(1);TreeNodenode2newTreeNode(2);TreeNodenode3newTreeNode(3);TreeNodenode4newTreeNode(4);TreeNodenode5newTreeNode(5);TreeNodenode6newTreeNode(6);root.leftnode2;root.rightnode3;node2.leftnode4;node2.rightnode5;node3.rightnode6;returnroot;}publicstaticvoidpreorder(TreeNoderoot){if(rootnull){return;}System.out.print(root.val );preorder(root.left);preorder(root.right);}publicstaticvoidinorder(TreeNoderoot){if(rootnull){return;}inorder(root.left);System.out.print(root.val );inorder(root.right);}publicstaticvoidpostorder(TreeNoderoot){if(rootnull){return;}postorder(root.left);postorder(root.right);System.out.print(root.val );}publicstaticvoidlevelOrder(TreeNoderoot){if(rootnull){return;}QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.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){TreeNoderootbuildTree();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 - 110.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(rootnull){return;}这就是递归的终止条件。如果没有这个判断递归会一直往下访问空节点最终出现空指针异常。11.4 普通二叉树适合用数组存吗一般不适合。数组存储适合完全二叉树因为下标关系连续不会浪费太多空间。普通二叉树如果结构比较偏比如只有右孩子就会导致数组中出现大量空位置空间浪费比较明显。所以普通二叉树更常用链式存储。十二、相关OJ题目相关OJ题目详见Java数据结构——二叉树相关OJ题目详解end*