树与二叉树

树的定义

树(Tree)默认指有根树(Rooted Tree)，无根树(Unrooted Tree)之后会在图结构(Graph)中讨论。树是种非线性结构，树中的元素一般称为树节点(Tree Node)，线性表元素的前驱后继是空或唯一的，一个树节点可以有不止一个“后继节点”，“前驱节点”是空或唯一的。给出树\(T\)的递归定义如下，递归定义法在算法中经常使用到：

1) \(T\)是由\(n\geq 0\)个节点(Node)组成的有限集合；

2) 当\(n=0\)时，\(T\)是空集称为空树；

3) 当\(n\geq 1\)时，\(T\)有且仅有1个节点被指定为\(T\)的树根(Root)；

4) 当\(n\geq 2\)时，\(T\)除树根外的所有节点被划入\(m\geq 1\)个不相交有限集合\(T_1,T_2…T_m\)(即它们的并集是\(T\)除树根外的所有节点，它们中任意2个的交集为空集)，并要求\(T_1,T_2…T_m\)都递归的满足树的定义，它们被称为\(T\)的子树(Subtree)；

可把树分成空树、仅有树根的树、有树根和子树的树。任何节点都是子树的树根，对于仅有树根的树(子树)，其树根被称为叶子节点(Leaf Node)。在树和子树中经常出现关于空树的“边界情况”，比如树\(T\)有\(m=100\)个子树，其节点数仅为\(n=2\)，\(T\)显然没有哪里不符合树的定义。于是这100个子树中一定有99个是空树，唯一的非空子树也仅有树根节点。

由于树的形式化定义比较抽象，人们会直观的“递归的画出树”，这种通用画法如上图所示，其中的虚线仅用来强调树与子树的包含关系，实际一般都不画虚线，因为无需虚线也能确定树与子树。在上述画法中，蓝色圈圈用来表示树中的所有节点。树(子树)\(T\)与\(T\)的所有子树的关系通过树边(Tree Edge)体现，当\(T\)有\(m\)个子树时，\(T\)的树根就会发出\(m\)条边分别连向这\(m\)个子树的子树根，叶子节点不会发出树边。注意到这里会遇到关于空树的问题，当\(T\)有子树时\(T\)一定有树根，但\(T\)的\(m\)个子树里不排除有空树，空树是没有树根的，那么该怎么处理\(T\)的树根到\(T\)的空子树的树边呢？一般有2种通用的处理方式：

1) 省略空子树与连向它的树边：这样得到的图像可能会“丢失”关于树的子树数目和空子树的“信息”，无法从图像中准确“还原”出所有子树的原定义，只有在确定不需要这些“信息”时才可以使用这种方式；

2) 使用nil假节点给空子树占位：当树(子树)\(T\)有\(n\)个空子树时，就画\(n\)个nil节点，并让\(T\)的树根发出\(n\)条边连向它们。这样得到的图像不丢失“信息”，可完整反推每个子树的原定义。需要注意的是，根据定义，不存在只有连向nil节点的节点；

在上述定义中，树的子树间是没有序关系的，这样的树称为无序树(Unordered Tree)，如果递归的要求树记录其所有子树的序，则是有序树(Ordered Tree)。画有序树时，树的所有子树的树根(或者nil)必须按序从左到右排列。对于有序树，显式画出nil节点显得更加重要，比如某树有5个子树，其中2个是空树，如果不画nil节点，那这3个非空子树是“1,2,3号子树”还是“2,3,5号子树”还是什么呢？一般认为树是有序树，处理无序树时将其当作有序树一般也没问题，反之则不一定。

为更好的描述节点的位置，人们通过亲缘关系形象描述节点的“相对位置”。在把树(子树)\(T\)的树根\(r\)称为父亲节点时，就把\(T\)所有子树的树根称为\(T\)或\(r\)的孩子节点，如果没有歧义也可直接称为孩子节点。而有相同父亲节点的孩子间可互称兄弟节点。从孩子的角度，孩子的父亲的兄弟称为叔叔节点，孩子的父亲的父亲称为祖父节点。总之只要能准确的实现相对定位，基本可以按这个规则称呼节点。一般节点的所有直系后代称为该节点的子孙，节点的所有直系长辈称为该节点的祖先。对于有序树还可以在称呼中体现序关系，比如“第5个孩子节点”，“第1个兄弟节点”等等，只要准确且无歧义即可。

还有种基于树的森林(Forest)结构，森林是由多个树组成的集合，记录树的序则是有序森林，否则是无序森林。

二叉树的定义

前面定义的树有个特点，就是每个子树的子树数目是不设限的，这里在此基础上递归的定义\(k\)叉树要么为空树，要么仅有一个叶子节点，要么有\(k\)个子树且这\(k\)个子树也都是\(k\)叉树，上图是3叉树的例子。如果画出\(k\)叉树，并显式的画出nil节点，那么对于其中的任意节点，要么不发出树边，要么发出\(k\)条树边。\(k=0\)时\(k\)叉树是空树或只有1个节点，\(k=1\)时\(k\)叉树等价于线性表，所以一般认为\(k=2\)时得到的是最简单的\(k\)叉树，称为二叉树(Binary Tree)。一般默认二叉树是有序树。

二叉树节点要么没有子树，要么有2个子树，有2个子树时可能有1个是空树，空树就可能需要用nil节点表示。不过考虑到二叉树比较简单，如果在画树边的时候显式的体现出“向左、向右”就无需画nil节点，也能区分出空子树，具体如上图所示。考虑到二叉树是有序的，一般称向左的边连向其左子树，向右的连向其右子树。或是称为左孩子和右孩子。当左子树或右子树为空，也称左孩子或右孩子为空，甚至对于叶子节点，也直接称其左子树和右子树都为空、左孩子和右孩子都为空。

需注意二叉树虽然是\(k\)叉树中最简单的，但二叉树是最重要的树结构，其应用十分广泛。因为很多问题都不需要那么多的“叉数”，通过研究二叉树得到的性质很多可直接推广至一般的树结构。

树与二叉树的表示与实现

在用程序实现数据结构时，一般不会直接根据定义实现。而是针对应用场景先确定对树的表示。比如对于线性表，数组就是种表示元素的序的方案，也是一种实现方案。这里给出树和二叉树的常用表示实现方案如下：

1) 孩子表示法：在节点上记录其所有子树的树根，给定树根节点即给定了整个树。是树与二叉树默认的表示和实现的方案。对于一般的树，可在节点中用不定长的动态表记录其子树根，比如该节点有10个子树，其中3个空树，那么就让动态表有10个槽，其中3个槽指向null即可，当该节点是叶子节点时，可以让动态表本身是空表(null)也可以让所有槽位都是null。对于\(k\)叉树，可在节点中用定长的\(k\)槽位的直接寻址表(数组)代替动态表。对于二叉树，用左指针\(left\)和右指针\(right\)即可表示，当某个子树为空时就让指针指向null，当节点为叶子节点时，不删掉这2个指针，而是让它们都指向null。注意到该表示法天然的能记录序关系，除非用集合代替上述动态表和直接寻址表。即使是无序树也能这样表示，只是不使用这些序关系而已；

2) 父亲表示法：在节点上记录其父亲节点，当且仅当节点为树根时其无父亲节点，给定所有节点的集合才能给定整个树。这种表示法最简单，每个节点只需要1个父亲指针\(parent\)即可，树根的\(parent\)指向null。这种表示法从任意节点出发都不保证“到达”所有其他节点，且不好区分子树间的序关系，除非给定所有节点时不用集合而是用线性表，但这也很难直接按第1个孩子、第2个孩子的方式去找节点。还有一个问题是不好处理空子树，如果想要强调空子树，需要用“真实节点(比如在节点里加入isNil变量)”表示nil节点，并让这个节点的\(parent\)指向其父亲节点。总之该法不常用；

3) 孩子兄弟表示法：用二叉树的孩子表示法表示一般的树。具体是让左指针表示“首个孩子”，右指针表示“下一个兄弟”，上图是具体的例子。这种表示法说明能建立二叉树与树的唯一互相转化的规则，两者能建立一一映射关系，并一定程度上表明能将树转化为二叉树来研究。当然想要实现这种完全唯一的转化时，也必须处理好对空子树的转化，不能丢失这部分信息。比如在上图中，有一个nil节点在二叉树中必须要成为“真实的nil节点”，因为它的右指针必须要指向下一个兄弟，将这个二叉树还原为树时，也要将这个“真实的nil节点”还原回去。该表示法同样天然的能记录序关系；

孩子表示法二叉树很像链表，所以其也被称为二叉链表。父亲表示法虽然作用有限，但其\(parent\)指针有时很有用，有时也在孩子表示法节点上加入\(parent\)指针。除上述表示法外，也能根据问题自己灵活确定表示方案，比如之后会讨论用线性表表示某种特殊二叉树的方法。至此尚未讨论树结构的任何运算，原因是树在各种应用场景中的作用差别比较大，一般没有统一的运算，并且这些运算相对复杂，更适合单独作为一个个模块讨论。下面是上述表示法的面向对象Python程序实现。