注意：这里是JAVA自学与了解的同步笔记与记录，如有问题欢迎指正说明

· 前言

一、一对多的结构：树形结构

二、二叉树

1.二叉树的体现运用

2.二叉树存储

三、二叉树遍历

1.树遍历的递归思想中的“三角抉择”

2.树的前、中、后序遍历

四、二叉树的深度与数目统计（4.1更新部分）

1.递归求解二叉树的数目

2.递归求解二叉树的深度

五、数据模拟

总结

· 前言

今天不知道为什么，写到博客一半的时候突然全部撤销了...后面怎么返回也恢复不了了。总之很郁闷，所以没办法...重新组织语言给大家说下我对于这部分的体会吧，而且今天内容又多，分两天给大家分享下吧。

一、一对多的结构：树形结构

一对多结构是一种非常常见的结构，我们可以在生活和实际的学习分析中常常看见这样的结构，例如无线局域网内的wifi路由器以一个网络管理多个主机，信道复用与分用，新冠病毒传染链...我们生活中处处可见一对多的特征，自然界也是如此，例如许多植物为了尽可能获得光合作用，会从一个茎向上尽可能多延伸出各种叶片，扩大植物的上部分的面积，这就是一种非常标准的一对多的延展现象。而我们计算机的先辈们也从中得到启示，将我们的一对多结构命名为：树形结构

在计算机邻域，我们为了具体分析树形结构，我通常用以下的简图来表示：

为了方便我们的实际语言描述，我们为这样的图示的树形结构赋予各种定义，例如树最顶部的发端口我们命名为树的根节点，以及沿用图论中的“度”的概念，但是我们通常在树中只考虑树体向下的边，也就是说，如果树的边是严格向下的有向图的话，我们在树中讨论的“度”都是结点的出度。这其中我们定义“度”为0的结点为叶子节点，而其余结点为叶子节点。而从根节点到任何一个结点的路径（边数和）我们称之为此结点的路径长度，而其中到叶子节点的路径长度往往是最长的，我们定义其中最长的叶子的路径长度为树的深度。

当然这些定义只是部分，若大家想了解完善的树形结构的一些基础概念大家可以具体查阅数据结构或者离散数学中的相关内容，这里不是我们主要的讨论点，便不多赘述。

二、二叉树

1.二叉树的体现运用

树形结构是灵活的，但是我们探究一些关键问题的时候，我们总是会在一些普遍结构中找特例，而其中二叉树（Binary tree）便应运而生。

所谓二叉树就是每个结点的度仅能是0、1、2，这种限制使得二叉树能够表现非常优良的接近二值化（Binary）的特性，同时能够简化树形结构的操作，在遍历手段上也更加简单。

首先要知道，计算机的存储体现是二值的，所以我们利用计算机解决现实问题的时候很多时候不得不考虑这些二进制（Binary）特性，因此二叉树便成为了一种非常方便的特性。

假如说，枚举有n个元素的集合的子集，那么逐个判断这个子集中的每个元素“有/无”来枚举是一种常见手段，但是另一方案就采用数据二值化思想。如果这个数据n=4，那么似乎就是枚举0000~1111全部的案例的过程，若我用二进制的眼光，只需要用int数据进行一次0到15的for循环，然后拆开每个int十进制的循环因子i内的二进制结构，bit为1则为“有”，bit为0则为“无”，那么就可以实现快速穷举。这就是位运算枚举法。

这个过程若你用图画出来就是一个向下延伸的二叉树。所以二叉树在基本上就具有枚举的特性，如果我们把这种枚举特性与树的权值特性结合起来完成一些最优问题，可以实现解决许多编码问题，例如前缀码技术和赫夫曼编码。此外包括想计算机网络当中的IP的CIDR编址分配和构成超网技术都利用了这种思想，算法中的深度搜索暴力递归枚举也都是这种思想，或者说，递归本质上都可以抽象为一个深度的递归树，只不过，递归选择宽度不同决定了递归树的结构存在差异。

2.二叉树存储

那么要实现存储二叉树要怎么做呢？首先说说顺序表，我们可以将二叉树按照逐层编号，然后存储依照编号存储于顺序表当中。这个方法是不错的，因为这样可以利用二叉树的优良数学与逻辑特性以及顺序表的存取特性实现每个结点父与子节点的快速访问，比如说，这种特性的逆过程就是我们堆排序的实现过程，实现了O(1)空间复杂度的O(NlogN)级排序。

当然这个方法有缺点吗？有！而且非常大，因为我们刚刚说的这种方案假设的是二叉树是一个完全二叉树时（具体不懂的，大家自行查阅吧），如果说这棵树并非完全二叉树，那么我们就要用特殊字符去对无效数据位进行填充，若我们构造的是不规则、复杂且深度极其深的树呢？比如下面仅有5个元素的深度为5的二叉树：

可见，为了有效存储这5个元素，我们需要花费18个存储空间的顺序表来存储。这种存储方式存储效率太低了。于是我们设法改用手段，第一种方法是还是使用顺序表，但是改用双亲表示法，但是这种方法受限于数据类型和使用场景，并不是我们大多数情况下遵循的最优已经最常规方法。于是乎，链表似乎成为了最佳的选择。

我们之前就提到过了，链表所表示的逻辑结构相邻的元素之间未必在实际物理存储中也相连，于是说，其就有优良的表示相对离散但是又具有相互固定关联性的某些逻辑结构，而树就是这种结构的完美案例：我们按照定义链表的风格定义，但是将链表域扩充一个，按照左右孩子的方式相连，如下：

Code：

	/*** The value in char.*/char value;/*** The left child.*/BinaryCharTree leftChild;/*** The right child.*/BinaryCharTree rightChild;/************************ The first constructor* * @param paraName The value.**********************/public BinaryCharTree(char paraName) {value = paraName;leftChild = null;rightChild = null;}// Of the constructor

同链表一样，初始化结点的指针域必须指空。

这样的表示方法不仅易于后续我们对于树形结构的操作，而且这种结构相比于顺序表模拟存储树形结构，更有树形的特征，体现了逻辑与物理的一致性。

三、二叉树遍历

二叉树的遍历不同于线性结构的遍历，因为我们在谈论线性结构遍历时，我们在逻辑上能非常容易想得通“ 从前到后 ”，“ 从后到前 ”这种逻辑性，因为这是符合我们现实生活中的逻辑的。但是一对多的结构我们却很难下意识反映出谁是“ 后 ”？谁是“ 前 ”，因此，我们需要规定一种手段，一种遍历的策略。举个鲜明的例子：散落在地上的一大堆碎片，如果你要数清楚到底散落了多少碎片，你的大脑就会下意识决定一种策略来避免数重复，比如从比较靠左的向右边的去数，从比较靠上的向下的去数。

对于二叉树，我们定义了四种基本手段：前序遍历、中序遍历、后续遍历、层次遍历。今天我们主要讲下前中后序遍历。

1.树遍历的递归思想中的“三角抉择”

树的遍历我们使用了递归的思想，我们默认将树的遍历简化为无数次“ 三角抉择 ” （为什么我取这个名字，因为我们的选择搞好构成个三角结构），每次遍历我们都会面临当前根结点、左子树、右子树的抉择：

这个时候我可以选择先遍历根结点，这个结点当前已知其确切值，可以直接遍历。当然现在也可以试着遍历左子树，但是因为左子树尚且不清楚，故要搁置当前的“ 三角抉择 ”而进入下一次“ 三角抉择 ”，也就是左子树的“ 三角抉择 ”。这个过程会不断持续，直到我们发现了叶结点，也就是当前的“ 三角抉择 ”只有根结点：

这个时候会仅仅遍历根结点，然后进行函数返回，进行回溯，返回到最近一次的“ 三角抉择 ” 并宣告完成某个模糊子树访问的任务。可见，这样的思想中我们使用了搁置当前选择的策略，这就正是递归操作的灵魂，也是栈的灵魂，更是树遍历的灵魂。

2.树的前、中、后序遍历

在说明清楚树遍历思想后，设计遍历代码就非常简单了，要知道，递归操作只要能简化为若干相同的操作后，那么代码就会变得非常间接。

首先，前序遍历（Preorder Traversal）采用的 “ 三角抉择 ”是：“根节点 - 左子树 - 右子树” (DLR)，翻译过来就是，首先，访问实际存在的实值——当前根节点；然后，若左子树存在，递归访问左子树；最后，若右子树存在，递归访问右子树。

Code：

	/************************ Pre-order visit.**********************/public void preOrderVisit() {System.out.print("" + value + " ");if (leftChild != null) {leftChild.preOrderVisit();} // Of ifif (rightChild != null) {rightChild.preOrderVisit();} // Of if}// Of preOrderVisit

简单来说，树的遍历无外乎就是这样的两个部分，即1.访问已知值 2.是对于未知的两个子树的接口访问。这其实非常满足我们之前推演的递归结构，或者说，是一种最简单的二路递归的结构。

那么后面两个遍历便水到渠成，中序遍历（Inorder Traversal）采用的 “ 三角抉择 ”是：“左子树 - 根节点 - 右子树” (LDR)。后序遍历（Postorder Traversal）采用的 “ 三角抉择 ”是：“左子树 - 右子树 - 根节点” (LRD)

Code：

	/************************ In-order visit.**********************/public void inOrderVisit() {if (leftChild != null) {leftChild.inOrderVisit();} // Of ifSystem.out.print("" + value + " ");if (rightChild != null) {rightChild.inOrderVisit();} // Of if}// Of inOrderVisit/************************ Post-order visit.**********************/public void postOrderVisit() {if (leftChild != null) {leftChild.postOrderVisit();} // Of ifif (rightChild != null) {rightChild.postOrderVisit();} // Of ifSystem.out.print("" + value + " ");}// Of postOrderVisit

不要看树的遍历多就认为一些遍历无用的，其实，它们都非常有用。前序遍历是树的深度优先搜索(DFS)，有着非常重要的作用，可以与后序遍历数一同完成波兰表达式的设计。中序遍历是排序树的遍历规则，是构成排序数以至于平衡树的根基。而后序遍历有非常完美的一个性质——记忆性，可以帮助树完成各种统计工作，例如交换子树，统计深度、数目，有非常优良的应用于现实问题的能力。

四、二叉树的深度与数目统计（4.1更新部分）

二叉树的深度与数目的统计就要非常灵活使用我们之前提到的二叉树的后序遍历的灵活性，因为我们可以把二叉树的这类统计操作用一种简单的递推表现出来，假如有个函数getCurNodes()可以获得本层我们需要的统计数据，而getLowerNodes()可以获得下层的数据统计，那么我们就可以通过getCurNodes() + getLowerNodes()得到以当前根为代表的树形结构的全部统计数据，而这个结果又可以作为其父级为根的树形结构的getLowerNodes()函数的一部分。

而在实际应用中我们更喜欢先计算getLowerNodes()，因为某些题目中getLowerNodes()的数据可能会给getCurNodes()带来一定的约束，解构来看，这是因为getLowerNodes()计算完毕后，我们能得知我们当前根为代表的子树的全部信息，这个时候我们需要的信息也会更加清晰。而往往我们getCurNodes()会需要这些信息，这就是后序遍历记忆性的运用。

当然我们求深度与数目不会用到这么复杂的约束，下面我先来看看求数目：

1.递归求解二叉树的数目

继承我们刚刚抽象的统计运算的求和式，关于求解二叉树的数目，getCurNodes()可以具体为“+1”，因为本层统计无非就计入当前的根的数目，二叉树时一对二的，故只能加一。而getLowerNodes()操作可细化为getLeftChild() + getRightChild()，这么来看可以得到我们的递归式：

$\large Sum{_{i}} = 1+getLeftChild{_{i}}\left ( \right ) + getRightChild{_{i}}\left ( \right )$

$\large getLeftChild{_{i}}\left ( \right ) = 1+getLeftChild{_{i+1}}\left ( \right ) + getRightChild{_{i+1}}\left ( \right )$

$\large getRightChild{_{i}}\left ( \right ) = 1+getLeftChild{_{i+1}}\left ( \right ) + getRightChild{_{i+1}}\left ( \right )$

当然，这个式子只是示意用的。我做了很多简化，这里补充下免得误解：1.我们省略和函数的参数，这个下标i只是简单示意层数用，第二个与第三个式子的 $getLeftChild{_{i+1}}\left ( \right )$ 与 $getRightChild{_{i+1}}\left ( \right )$ 并不一致，因为他们修饰的结点是不一样的。2.我们省略了边界条件，边界条件要视函数的结点参数本身来确定，如果说这个结点无左孩子便不统计 $getLeftChild{_{i+1}}\left ( \right )$ 计算，另外右孩子同理。通过上图的递推模拟，再结合我们前几天学习的递推算式转换为递归函数的万能方案，可以写出代码：

	/************************ Get the number of nodes.* * @return The number of nodes.**********************/public int getNumNodes() {// It is a leaf.if ((leftChild == null) && (rightChild == null)) {return 1;} // Of if// The number of nodes of the left child.int tempLeftNodes = 0;if (leftChild != null) {tempLeftNodes = leftChild.getNumNodes();} // Of if// The number of nodes of the right child.int tempRightNodes = 0;if (rightChild != null) {tempRightNodes = rightChild.getNumNodes();} // Of if// The total number of nodes.return tempLeftNodes + tempRightNodes + 1;}

2.递归求解二叉树的深度

有了之前的经验，深度问题似乎也可以迎刃而解了，只要明白树深度的特点：最长的那条到叶结点的路径长度。那么我们只需要修改getLowerNodes()的表示即可，当我们利用后序遍历知道了左子树的数目和右子树的数目时，我们没必要求和，而是选择用贪心的思想尽可能选择最长的那条边，只要我们每回合都选择最长的，那么最终我们得到就是最长的（因为每步都是稳定递增，故每次求局部最优解最终能保证全局最优解，这就是贪心），由此有下列递推（简化的思路同上）：

$\large Sum{_{i}} = 1+ MAX\left \{ getLeftChild{_{i}}\left ( \right ) , getRightChild{_{i}}\left ( \right ) \right \}$

$\large getLeftChild{_{i}}\left ( \right ) = 1+MAX\left \{ getLeftChild{_{i+1}}\left ( \right ), getRightChild{_{i+1}}\left ( \right ) \right \}$

$\large getRightChild{_{i}}\left ( \right ) = 1+MAX\left \{ getLeftChild{_{i+1}}\left ( \right ), getRightChild{_{i+1}}\left ( \right ) \right \}$

Code:

	/************************ Get the depth of the binary tree.* * @return The depth. It is 1 if there is only one node, i.e., the root.**********************/public int getDepth() {// It is a leaf.if ((leftChild == null) && (rightChild == null)) {return 1;} // Of if// The depth of the left child.int tempLeftDepth = 0;if (leftChild != null) {tempLeftDepth = leftChild.getDepth();} // Of if// The depth of the right child.int tempRightDepth = 0;if (rightChild != null) {tempRightDepth = rightChild.getDepth();} // Of if// The depth should increment by 1.if (tempLeftDepth >= tempRightDepth) {return tempLeftDepth + 1;} else {return tempRightDepth + 1;} // Of if}// Of getDepth

总之，求解树的统计类问题往往就是递归的运用，一定要用递归的思想去分析。

五、数据模拟

我们用简易的手工方式构造下面这样的二叉树：

Code：

	/************************ Mannually construct a tree. Only for testing.**********************/public static BinaryCharTree manualConstructTree() {// Step 1. Construuct a tree with only one node.BinaryCharTree resultTree = new BinaryCharTree('a');// Step 2. Construct all nodes. The first node is the root.BinaryCharTree tempTreeB = new BinaryCharTree('b');BinaryCharTree tempTreeC = new BinaryCharTree('c');BinaryCharTree tempTreeD = new BinaryCharTree('d');BinaryCharTree tempTreeE = new BinaryCharTree('e');BinaryCharTree tempTreeF = new BinaryCharTree('f');BinaryCharTree tempTreeG = new BinaryCharTree('g');// Step 3. Link all nodes.resultTree.leftChild = tempTreeB;resultTree.rightChild = tempTreeC;tempTreeB.rightChild = tempTreeD;tempTreeC.leftChild = tempTreeE;tempTreeD.leftChild = tempTreeF;tempTreeD.rightChild = tempTreeG;return resultTree;}// Of manualConstructTree

执行模拟的代码（分别执行前中后序遍历与求深度和树结点数目）：

	/************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {BinaryCharTree tempTree = manualConstructTree();System.out.println("\r\nPreorder visit:");tempTree.preOrderVisit();System.out.println("\r\nIn-order visit:");tempTree.inOrderVisit();System.out.println("\r\nPost-order visit:");tempTree.postOrderVisit();System.out.println("\r\n\r\nThe depth is: " + tempTree.getDepth());System.out.println("The number of nodes is: " + tempTree.getNumNodes());}// Of main

执行结果：

总结

今天的文章我用了大篇幅来介绍树的思想来源以及二叉树的存储来由，遍历的来由。一方面是为了把树这么重要的一个结构讲清楚，另一方面也是对我对这部分的自我理解做个小结和汇总。

树形结构确实太重要了，一方面，它是个至关重要的思想，其蕴含递归的层次化思想，分治细化的思想，同时还有分类的功能。另一方面它又是个至关重要的工具，在编码领域有信息学的赫夫曼编码、前缀码；计算机网络领域有IP的CIDR编址、构成超网、最简路由避免兜圈的方案，以及局域网的树状网络拓扑结构；组成原理的操作字可变编码，从而缩小编码范围，扩大寻址空间；操作系统中我们现代操作系统普遍的多级层次文件管理系统；另外，还有我在本文提到的二叉树在枚举方面的运用。

一个简单的树形结构的运用就可以几乎把计算机有关大部分学科给串联了起来，可见人们是多么喜欢这样的数据结构：优良的逻辑特性，易于表现的存储方案，完美的递归结构，完美逻辑建模思路。

今天我们主要讲述了树的常规使用方法（遍历、基础统计），不难发现了，用好树形结构的一个关键途径在于是如何利用好递归的思想。递归思想具有很好处理前后具有一对多或多对多信息关联的数据，而我们树形结构正好对了他的胃口。因此，想学好使用树形结构，要找准合理的递归技巧才行；相对的，我相信在学习树的过程中，渐渐地，一个人对于递归的理解也会渐渐建立起来。