【CPP】各种各样的树（4）——线索二叉树

上次说了几个二叉树，想必也能发现二叉树的两大缺陷。1.二叉树在遍历的时候要使用到递归，如前所说，虽然递归可以使代码看起来更简洁易懂，但递归是十分耗费资源的操作，我们希望可以避免使用它。2.二叉树的叶子结点，单子结点等结点总存留有空的指针域，实际上达到了n+1个，这造成了空间的浪费，我们希望可以利用起这些空间。这样的思考便引出了线索二叉树。

线索二叉树，如名所示，是按照目标的遍历顺序将各个结点利用名为Thread（线索）的指针链在一起的数据结构，效果仍然类似于封面。这些名为线索的指针我们将其存放在二叉树原有的空指针域中，然后当我们想重新来遍历二叉树时，我们便可以利用这些线索来用非递归的算法遍历它。这样我们又利用了空指针又解决了递归的问题，线索的连接我们只需要在开始时对二叉树进行线索化，利用一次递归来放置好线索即可。对于线索二叉树我们需要在通常的二叉树结点上增加两个bool型的标志域用来表示左右指针是线索（Thread）还是链接（Link），这只是小开销，和获得的收益比没什么。

首先是结点与树的声明。

在树的声明中，增加了p_pre的全局前指针，这是线索化时的重要工具，然后将两个线索化的递归函数私有，对外保持线索化的驱动函数。树的插入函数仍是之前二叉查找树的插入。

然后先来看看中序线索遍历。

注释中讲了中序线索化的原理和中序遍历线索树的原理，在写这段代码时要想象一棵二叉树并按照递归遍历的顺序为它安上线索，在遍历时要注意输出数据的时机。被成功中序线索化后的二叉树可以较轻松地从一个结点寻找到其他的结点无论是父节点还是子结点，这也是线索化的好处之一。

然后是原理类似的前序线索化，在平时使用中，中序线索化是比较重要的，前序线索化主要是更改了递归的时机和遍历方式，驱动函数则没有变化。

在理解中序线索二叉树的情况下，先序线索二叉树想来也没那么难以理解了。这里是测试的主函数和效果。

然后就要提到后序线索二叉树。后序线索二叉树比较特别，由于后序（后根）遍历规则的问题，实际上我们的结点是需要去寻找它们的父节点的，因为是先子后根的顺序。如果是叶子结点或者有剩余空指针域的结点，我们自然可以很轻松地用线索链至其父结点。但是如果结点本身没有空指针域了问题就出现了，我们没有办法在不改动原先结点结构的情况下来访问其父节点，这要怎么办呢？

后序线索二叉树本身是不完善的，我们要么引入一个栈，利用栈来保存这些结点的父节点，要么给每个结点增加一个专门指向父节点（parent）的指针域。但是这两种方法都不好，第一种让遍历变成了递归的简化，第二种实际上并没有办法减少空指针域，有了父节点指针域的树也变成了双向链表，破坏了原本的二叉树，这都不是什么好的办法。

那怎么办呢？寻找了一段时间的方法，网上有提到反向遍历的方法，但是实践代码总不成功，关于后序遍历的线索二叉树一般都说是无法常规实现的，只能暂且放下它吧。( ´･･)ﾉ(._.`)

说完了线索二叉树，就该来解决在二叉查找树中提出的问题，二叉树不平衡导致查找时间增加怎么办？接下来来讲最先发明的一种自平衡二叉查找树——AVL树。