散文精选网线索二叉树
为什么需要线索二叉树呢？
正如程序猿发觉单链表并不总能满足某些程序设计的要求时，发明了双向链表来弥补一样，线索二叉树也是在需求中被创造的！
那普通的二叉树到底有什么缺陷让我们发指呢？
一，浪费空间、二，浪费时间、三，浪费青春
为了明白为什么要创造线索二叉树，看一道数数题：请问以下有多少个“^”？总共浪费了多少字节的空间？(32bit的机器)
小禹禹肯定心里有数啦，点击查看
(点击空白处查看内容)
▼
包含10个“^”，32bit的机器，8bit一个字节，一个 “^”占4个字节，总共浪费了40个字节！
对于一个有n个节点的二叉链表，每个节点有指向左右节点的2个指针域，整个二叉链表存在2n个指针域。而n个节点的二叉链表有n-1条分支线，那么空指针域的个数=2n-(n-1) = n+1个空指针域，从存储空间的角度来看，这n+1个空指针域浪费了内存资源。
我们知道通过对二叉树的约定遍历方式，可以得到一个固定的遍历顺序，那么请问哪种遍历方式可以节省 “ ^ ” 所浪费的空间？（利用“^”记录该结点的前驱后继结点），自己可以根据上面的图回顾一下前中后三种遍历方式，再看下面奥！
中序遍历后结果是：HDIBEAFCG
红色的结点都是刚才“ ^ ”造成浪费的结点，中序遍历结果中它们刚好均处于字符中间，可以很好地利用“ ^ ”来存放前驱和后继的指针。
不过好事总是多磨的，我们是有主观意识所以可以很容易看出来哪些结点可以利用存放前驱后继。
可能有的小禹禹就不同意了：这所谓的主观意识还不简单，不就是从第一个开始每隔一个结点就可以？
上图中的中序遍历结果为：HDIBACG，其中蓝色三角标注的是只有一个空闲的指针位置，如果是这样的话我们就面临一个问题：机器怎么识别到底是存放指针还是线索？
没错，她需要一丁点儿提示，为此我们将已经定义好的结构进行“扩容”：
ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rtag为0时指向该结点的右孩子，为1时指向该结点的后继。
综合以上面的分析，可以通过充分利用二叉链表中的空指针域，存放节点在某种遍历方式下的前驱和后继节点的指针。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，对应的二叉树就称为“线索二叉树(Threaded Binary Tree)” 。
我们对二叉树进行中序遍历（不了解二叉树遍历请参考 《一文横扫二叉树的所有遍历方法》），将所有的节点右子节点为空的指针域指向它的后继节点。将这颗二叉树的所有节点左指针域为空的指针域指向它的前驱节点，得到如下图所示结果：
动画理解
播放C语言主要实现代码：
// 全局变量，始终指向刚刚访问过的结点
BiThrTree pre;
// 中序遍历线索化
void InThreading(BiThrTree T)
{
if( T )
{
InThreading( T->lchild ); // 递归左孩子线索化
if( !T->lchild ) // 如果该结点没有左孩子，设置ltag为Thread，并把lchild指向刚刚访问的结点。
{
T->ltag = Thread;
T->lchild = pre;
}
if( !pre->rchild )
{
pre->rtag = Thread;
pre->rchild = T;
}
pre = T;
InThreading( T->rchild ); // 递归右孩子线索化
}
}
void InOrderThreading( BiThrTree *p, BiThrTree T )
{
*p = (BiThrTree)malloc(sizeof(BiThrNode));
(*p)->ltag = Link;
(*p)->rtag = Thread;
(*p)->rchild = *p;
if( !T )
{
(*p)->lchild = *p;
}
else
{
(*p)->lchild = T;
pre = *p;
InThreading(T);
pre->rchild = *p;
pre->rtag = Thread;
(*p)->rchild = pre;
}
}
Java 语言主要实现代码
/**
* 中序线索化二叉树
*/
void inThreadOrder(Node node) {
if(node == null) {
return;
}
//处理左子树
inThreadOrder(node.left);
//左指针为空,将左指针指向前驱节点
if(node.left == null) {
node.left = preNode;
node.isLeftThread = true;
}
//前一个节点的后继节点指向当前节点
if(preNode != null && preNode.right == null) {
preNode.right = node;
preNode.isRightThread = true;
}
preNode = node;
//处理右子树
inThreadOrder(node.right);
}
你好呀！由于一篇图文只能插入三个视频，但还有三个视频，我给大家放到了第二篇图文中，如果你需要线性表的 flash 演示动画，你可以后台回复 “线性表” 获得两篇图文中的所有的 flash 动画资料。
推荐阅读
一文横扫二叉树的所有遍历方法
一文读懂有关Tree的前世今生
END
作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。
