6.5.3 线索链表的生成

算法 算法6.10
　　void InThreading(BiThrTree p，BiThrTree& pre)
　{
　　// 对 p 指向根结点的二叉树进行中序遍历，遍历过程中进行"中序线索
　　// 化"。若 p 所指结点的左指针为空，则将它改为"左线索"，若 pre
　　// 所指结点的右指针为空，则将它改为"右线索"。指针 pre 在遍历
　　// 过程中紧随其后，即始终指向 p 所指结点在中序序列中的前驱。
　　if (p) {
　　　InThreading(p->Lchild, pre);　　　　　　　// 对左子树进行线索化
　　　if (!p->Lchild)
　　　　{ p->LTag = Thread; p->Lchild = pre; }　// 建前驱线索
　　　if (!pre->Rchild)
　　　　{ pre->RTag = Thread; pre->Rchild = p; }// 建后继线索
　　　pre = p;　　　　　　　　　　　　　　　　// 保持 pre 指向 p 的前驱
　　　InThreading(p->Rchild, pre);　　　　　　 // 对右子树进行线索化
　　} // if
　} // InThreading

算法 算法6.11
　　void InOrderThreading(BiThrTree &Thead, BiThrTree BT)
　{
　　// BT为指向二叉树根结点的指针，由此二叉链表建立二叉树
　　// 的中序线索链表，Thead 指向线索链表中的头结点。
　　BiThrTree pre;
　　if (!(Thead = new BiThrNode)) exit (1); // 存储分配失败
　　Thead->LTag = Link; Thead->RTag =Thread;　// 建头结点
　　Thead->Rchild = Thead;　　　　　　　　　// 右指针回指
　　if (!BT) Thead->Lchild = Thead; 　　　　// 若二叉树空，则左指针回指
　　else {
　　　Thead->Lchild = BT; pre = Thead;
　　　InThreading(BT, pre); 　　　　　　　　// 中序遍历进行中序线索化
　　　pre->Rchild = Thead; pre->RTag = Thead;
　　　　　　　　　　　　　　　　　// 对中序序列中最后一个结点进行线索化
　　　Thead->Rchild = pre; 　　　　　　　　// 建非空树的头结点的"右线索"
　　} // else
　} // InOrderThreading
  

　　请结合上例线索链表建立过程的动画演示 动画 理解算法6.11和算法6.10的执行过程。特别注意，遍历过程中指针 p 和 pre 的变化过程。

  思考题 建立先序线索链表或后序线索链表的算法和建立中序线索链表的算法有何不同？