关于二叉树的那些事

# 一 前言 没有良好的数据结构基础根本支持不起深度研究，故知识追寻者发了大力气写一篇通俗易懂的树概念，希望读者们可以收获颇多；本篇文章将带领读者理解什么是树，树具有哪些特性，常见树的类别，简单实现等，尊重原创，转载请联系知识追寻者，知识追寻者系列文章仅供个人学习，不得用于商业用途； # 二 树的概念与特性 ## 2.1 树的概念 树是类似于链表的线性结构，但又是一种典型的非线性的结构；树具有很强的层级性，相比于线性结构，其时间复杂度更低，效率更高；读者可以联系，生活中看见的树； ## 2.2 树的术语 先看一张树的图片如下，去除图中的箭头和相关术语，**树就是一种非线性的层级结构**；  树的相关术语如下： - **根节点**： 没有父节点的节点，上图 A节点； - **兄弟节点**：具有相同的父节点的孩子节点；比如 F,G互为兄弟节点； - **叶子节点**：`没有孩子节点的节点`；比如D,F,G,I,J； - **祖先节点与孙节点**：如果存在根节点A到节点 J 的路径，并且存在节点E出现在该路径上，则称E是节点 J 的祖先节点，J是 E 的孙节点；A B E H 都可以算是 J 的祖先节点； - **节点大小**：节点的大小是指节点`拥护的孙节点个数`，包括自身； 比如E 节点大小为4； - **节点的深度**：指根节点到节点的`路径长度` ； 比如 (A-B-D ), 两个 链，即D节点的深度为2； - **节点的高度**：指节点到最深节点的 `路径长度`；比如 (E - H -J), 两个链, 即E节点的高度为2； - **树的层级**：具有相同深度的集合称为树的层级；比如 B和C ； 又比如 D,E,F,G - **树的高度和深度**： 树的深度指所有节点中深度的最大值，树的高度指所有节点中高度的最大值；`树的高度等于树的深度` ## 2.3 树的类型 二叉树： 如果一棵树中每个节点有0个或者1个或者2个节点，则称该树为二叉树；故空树也是二叉树； > 严格二叉树: 树的每个节点都有左孩子右孩子或者没有孩子；  > 斜树：斜树的每个节点只有一个孩子；若斜树的每个节点都只有左孩子则称为左斜树，若斜树的每个节点只有右孩子则称为右斜树；  > 满二叉树：所有的父节点都存在左孩子和右孩子，并且所有的叶子结点都在同一层上，则称该类树为满二叉树  > 完全二叉树：对于一棵具有n个节点的二叉树**按照层级编号**，同时，**左右孩子按照先左孩子后右孩子编号**，如果编号为i的节点**与**同样深度的满二叉树中编号为i的节点在**二叉树中的位置完全相同**，则这棵二叉树称为完全二叉树；故满二叉树一定是完全二叉树，反之不成立  ## 2.4满二叉树的性质 > 满叉树的节点个数: 假设满二叉树层级为k，根据 数学归纳法和等比数列求和公式可得 2^0 + 2^1 +...+ 2^k = 2^(k+1) - 1; 推导过程如下图； > > 满二叉树的叶子节点个数：根据满二叉树的结构可知，第k层就是叶子节点所在的层，故叶子节点个数为 2^k个  # 三 二叉树的实现 ## 3.1 二叉树的结构 根据二叉树的结构可知，每个节点都可以假设有左孩子和右孩子，则可以对应为 左指针和右指针，并且每个节点上都可以存储值；故经过面向对象的编程思想进行抽象后的类如下 ``` /** * @Author lsc *

二叉树的结构

*/ public class TreeNode { // 左孩子 private TreeNode leftNode; // 右孩子 private TreeNode rightNode; // 存储值 private Object value; // 构造方法 TreeNode(Object value){ this.value = value; } // 省略 set get } ``` 现在需要实现以下的一颗满二叉树;  思路如下： 首先根节点储存1；然后分别储存 左孩子2，右孩子3； 其次左孩子节点作为父节点，然后分别储存 左孩子4，右孩子5； 最后右孩子节点作为父节点然后分别储存 左孩子6，右孩子7； 代码实现如下： ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); } public static TreeNode initTree(){ // 创建7个节点 TreeNode treeNode1 = new TreeNode(1); TreeNode treeNode2 = new TreeNode(2); TreeNode treeNode3 = new TreeNode(3); TreeNode treeNode4 = new TreeNode(4); TreeNode treeNode5 = new TreeNode(5); TreeNode treeNode6 = new TreeNode(6); TreeNode treeNode7 = new TreeNode(7); // 根据上面思路对节点进行组装 // 组装根节点 treeNode1.setLeftNode(treeNode2); treeNode1.setRightNode(treeNode3); // 组装左孩子 treeNode2.setLeftNode(treeNode4); treeNode2.setRightNode(treeNode5); // 组装右孩子 treeNode3.setLeftNode(treeNode6); treeNode3.setRightNode(treeNode7); return treeNode1; } ``` ## 3.2 二叉树的遍历与实现 二叉树的遍历分为前序遍历，中序遍历，后续遍历；假设 当前节点 为C (Current Node), 左节点为L ,右节点为R； > 前序遍历：C----->L------->R > > 中序遍历：L----->C------->R > > 后续遍历：R----->C------>L **先序遍历的实现** 思路 ： - 首先访问当前节点； - 其次访问左节点； - 最后访问后节点； 回到 前图 前序遍历CLR就是 1，2，4，5，3，6，7； ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); // 调用先序遍历 preOrderTree(tree); } /* * * @Author lsc *

先序遍历

* @Param [rootNode] * @Return void */ public static void preOrderTree(TreeNode rootNode){ if (rootNode!=null){ // 值 System.out.println(rootNode.getValue()); // 左孩子 preOrderTree(rootNode.getLeftNode()); // 右孩子 preOrderTree(rootNode.getRightNode()); } } ``` 输出 ``` 1 2 4 5 3 6 7 ``` 先序遍历实现为线性实现，时间复杂度为O(n) **中序遍历的实现** 思路 ： - 首先访问左节点 - 其次访问当前节点 - 最后访问右节点 回到 前图中序遍历的结果是 4，2，5，1， 6，3，7 ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); // 调用中序遍历 middleOrderTree(tree); } /* * * @Author lsc *

中序遍历

* @Param [rootNode] * @Return void */ public static void middleOrderTree(TreeNode rootNode){ if (rootNode!=null){ // 左孩子 middleOrderTree(rootNode.getLeftNode()); // 值 System.out.println(rootNode.getValue()); // 右孩子 middleOrderTree(rootNode.getRightNode()); } } ``` 输出 ``` 4 2 5 1 6 3 7 ``` 中序遍历实现为线性实现，时间复杂度为O(n) **后续遍历的实现** 思路： - 首先访问左节点 - 其次访问右节点 - 最后访问当前节点 回到 前图中序遍历的结果是 4，5，2，6， 7，3，1 ``` public static void main(String[] args) { // 初始化树 TreeNode tree = initTree(); // 调用后续遍历 postOrderTree(tree); } /* * * @Author lsc *

后续遍历

* @Param [rootNode] * @Return void */ public static void postOrderTree(TreeNode rootNode){ if (rootNode!=null){ // 左孩子 postOrderTree(rootNode.getLeftNode()); // 右孩子 postOrderTree(rootNode.getRightNode()); // 值 System.out.println(rootNode.getValue()); } } ``` 输出 ``` 4 5 2 6 7 3 1 ``` 后序遍历实现为线性实现，时间复杂度为O(n)