在上一篇文章中，我们学习了二叉树的基本链式结构和树的构建和遍历相关的操作。今天我们学习一些与二叉树相关的概念以及二叉树的一种变体。完全二叉树什么是完全二叉树？在说完全二叉树之前，我们先来说说另一个名词：“满二叉树”。我们上一篇文章演示的二叉树是“满二叉树”。在这棵树中，所有节点都有两个子节点，没有一个节点只有一个子节点，并且所有的底部叶子节点都在同一层，这种树称为“满二叉树”，也称为“完美二叉树””。这不是一棵美丽的树吗？没错，这棵二叉树非常完美，它没有多余的节点，也没有缺失的节点，非常漂亮。然而现实中，完美的东西是非常难得的，人生总会有一些遗憾。我们尽量不让自己有太多的缺点，但我们永远不可能活得没有一丝缺点。因此，我们允许叶子节点出现在最低层和次低层，并且最低层的叶子节点集中在树的左边，即叶子节点只能有左子树。该树称为“完全二叉树”。不要担心它不完美，因为这样一个稍有瑕疵的生命就是完整的，所以“完全二叉树”是一种理想的树结构。从定义上我们可以看出，“满二叉树”一定是“完全二叉树”，而“完全二叉树”的叶子节点都在一个层次上，所有节点都有左右子节点“即一棵“满二叉树”。为什么要讲“满二叉树”和“完全二叉树”呢？当然是为我们接下来的内容做铺垫。因为“满二叉树”是最符合性质的树还记得树系列第一篇介绍的二叉树的5个性质吗？当时我们以“满二叉树”为例进行讲解，其中性质5是我们的基础学习使用时序结构存储二叉树二叉树的时序存储利用了“满二叉树”的概念和二叉树的性质5.我们可以实现使用数组存储时序结构的实现.$treeList=['','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O'];相信大家都不陌生。在上一篇文章中，我们使用这个数组构建了一棵链式树，而这个数组其实就是一个线性存储的二叉树。我们通过对比二叉树的性质5来看一下。节点A的下标是1，这是我们的树根。它的子节点是B和C，对应的下标是2和3，即12和12+1。同样，我们选择另一个节点F，它的下标是6，所以它的左子节点的下标是62=12，对应L；它的右子节点是62+1=13，对应于M。反之，一个节点的父节点是i/2。我们看节点K的下标是11，它的父节点是11/2，小数点是下标5的位置，就是节点E；节点J的下标为10，它的父节点节点为10/2，也就是下标为5的E节点。现在想必大家都明白怎么用数组来表示二叉树结构了吧。而且数组的结构更加一维，更能体现树的操作是二维一维的一种表示，即非线性到线性的转换，这样我们就可以方便的操作这些数据.对于顺序存储结构，即数组元素的遍历，也可以采用前序、中序、后序、层序的形式。但是，这些遍历方式都需要根据二叉树的性质5进行遍历。但更重要的是，只要给我一个下标，我们就可以很容易的通过二叉树的属性知道它的下级节点和上级节点的位置，可以快速的获取到这些节点的信息。这个特性在链式二叉树中是没有的。如果我们要存储的不是“满二叉树”怎么办？即使不是完全二叉树，也只需要将对应的节点设置为空值即可。例如：$treeList=['','A','B','C','D','E','I','','','','','H','','J','',''];这棵树的结构对应的二叉树图是这样的：那么在构建链接树的方法中，我们只需要再增加一个判断即可。我们可以通过这样一个顺序存储的二叉树，快速生成一个链式存储的二叉树，方便我们后续的操作。//创建二叉树functionCreateBiTree($arr,$i){if(!isset($arr[$i])||!$arr[$i]){//在这里添加判断，如果数组元素为空返回null；}$t=新的TBTNode();$t->数据=$arr[$i];$t->lChild=CreateBiTree($arr,$i*2);$t->rChild=CreateBiTree($arr,$i*2+1);return$t;}线索二叉树是一个环，接下来我们讲“线索二叉树”。这是什么？从上面的学习，我们知道了“满二叉树”和“完全二叉树”。但这种结构是一种非常理想的树形结构，而真实情况可能大多是“理想很丰满，现实很骨感”。很多树都无法形成这样的完备二叉树，更谈不上“满二叉树”了。树遍历通常使用堆栈或队列来实现。这两种遍历方式基本是线性的，即最佳情况下的时间复杂度为O(n)。那么，有没有更快的方法来提高遍历的效率呢？试一下：如果树的叶子节点的左子节点为空，就让它指向前驱（上级）节点如果树的叶子节点的右子节点为空，就让它指向后继node这样做有什么好处？我们可以避免大量的递归操作，从而加快树的遍历。在整个算法中，它没有任何优势，因为我们需要对一棵树进行线程化，也就是改变它的叶子节点的左右孩子的方向，这也是一种遍历。但是，如果你的操作经常需要遍历，而且是多次来回遍历，那么它的综合性能要比普通的二叉树遍历强。因为在一个线程之后，它的遍历是在快速找到叶子节点的基础上进行普通的线性遍历操作，而不是递归操作。对于线程二叉树，我们需要改变树的节点存储数据结构。//线程二叉树节点类TBTNode{public$data;公共$lTag=0;公共$rTag=0;公共$lChild；public$rChild;}我们增加了两个标志位，当$lTag或$rTag为1时，$lChild或$rChild分别指向前驱节点或后继节点。这样，在最后的遍历过程中，我们可以通过标记标志位快速区分节点的指向状态。那么我们先简单的建一棵树。使用上一节中的示例。//创建二叉树functionCreateBiTree($arr,$i){if(!isset($arr[$i])||!$arr[$i]){//在这里添加判断，如果数组元素为空返回null；}$t=新的TBTNode();$t->数据=$arr[$i];$t->lChild=CreateBiTree($arr,$i*2);$t->rChild=CreateBiTree($arr,$i*2+1);返回$t;}$treeList=['','A','B','C','D','E','I','','','','','H','','J','',''];$tree=CreateBiTree($treeList,1);下一步是最重要的线索过程，我们可以创建前序、中序和后序线索的二叉树。相应的，上一次线程二叉树遍历得到的结果也将是三种遍历方式对应的结果。在这里，我们学习最常见最经典的“中序线程二叉树”。因此，我们以中序遍历的形式对这棵树进行线程化。//线程函数InThread(?TBTNode$p,?TBTNode&$pre){if($p){//递归，左子树线程InThread($p->lChild,$pre);if(!$p->lChild){//创建当前节点的前驱线程$p->lChild=$pre;$p->lTag=1;}if($pre&&!$pre->rChild){//创建当前节点Node的后继线索$pre->rChild=$p;$pre->rTag=1;}$pre=$p;//$pre指向当前$p，作为$p将指向的下一个节点Predecessor节点指针$p=$p->rChild;//$p指向一个新的节点，$pre和$p指向的节点分别组成前驱-后继对，为下一次线程做准备//递归，右子树线程InThread($p,$pre);}}//创建线程二叉树函数createInThread(TBTNode$root){$pre=null;//前驱节点指针if($root){InThread($root,$pre);$pre->rChild=null;//非空二叉树，线程$pre->rTag=1;//后处理顺序中的最后一个节点}}createInThread($tree);var_dump($tree);//object(TBTNode)#1(5){//["data"]=>//string(1)"A"//["lTag"]=>//int(0)//["rTag"]=>//int(0)//["lChild"]=>//object(TBTNode)#2(5){//["data"]=>//string(1)"B"//["lTag"]=>//int(0)//["rTag"]=>//int(0)//["lChild"]=>//对象(TBTNode)#3(5){//["data"]=>//string(1)"D"//["lTag"]=>//int(1)//["rTag"]=>//int(1)//["lChild"]=>//NULL//["rChild"]=>//*RECURSION*//}//...算法的具体步骤在注释里写的很详细，一句话总结就是在中序遍历的过程中，根据结点的信息判断其左右孩子的形式，如果有左右孩子，继续，如果没有孩子，就指向左右孩子到前驱或后继。建立后的线索二叉树如图：最后就是遍历。我们需要的是能够快速获取到最左边叶子节点的信息，然后是下一跳的信息.这个时候，线索的力量就发挥出来了。//在以$p为根的inorder线程二叉树中，inorder序列下的第一个节点为最左边的节点functionFirst(?TBTNode$p){while($p->lTag==0){$p=$p->l孩子;//左下节点（不一定是叶节点）}return$p;}//在中序二叉树中，中序节点函数中节点$p的后继节点NextNode(?TBTNode$p){if($p->rTag==0){返回第一个($p->rChild);}else{返回$p->rChild;//ifrTag==1,直接返回后继线程}}//对中序线程二叉树进行中序遍历functionInorder(TBTNode$root){//第一个节点不为空下一个节点for($p=First($root);$p;$p=NextNode($p)){echo$p->data,',';}}中序（$树）；//D,B,E,H,A,I,J,C，当遇到$lTag不为0的节点时，该节点为最左边的节点，如果不为空，则[输出]它。然后我们得到下一跳的节点，也就是判断这个节点右孩子的$rTag标志。如果为0，即有右孩子。【输出】并向下查找，直到找到一个$rTag也为1的节点，直接返回这个节点的后继，即中序遍历的中间节点，【输出】它。最后输出的顺序是不是和我们中序遍历的结果一样？注意代码。在遍历中序线程二叉树时，我们没有使用递归。我们全部使用了while()和for()来完成线程二叉树的遍历。总结坚持到现在已经很不容易了，所以我们不能再小看数据结构了对吧？现在它只是一棵树，我们的图还没有开始呢！当然，不要害怕，循序渐进地学习，慢慢掌握，不要幻想一口气变胖。写完这篇文章，我不可能马上手写一个中序线索二叉树。大家还是以理解原理为主。真的会手写的话，一定要背下来面试或者备考考研。面试的时候要多问一些关于这样的年轻学生的问题。毕竟，即兴的准备远不如深入了解带来的感悟！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/4.tree/source/4.3完全二叉树、线索二叉树和树顺序存储结构.php参考资料：《数据结构》第二版、闫伟民《数据结构》第二版、陈越《数据结构高分笔记》2020年版，天琴考研各媒体平台均可搜索【硬核项目经理】
