遍历2叉树是按1定的规则将树中的结点排列成1个线性序列，即是对非线性结构的线性化操作。
如何找到遍历进程中动态得到的每一个结点的直接先驱和直接后继(第1个和最后1个除外)?如何保存这些信息?
问：1棵有n个结点的2叉树，有多少个空闲指针域未用？
若1棵2叉树有n个结点，则有n⑴条指针连线 ， 而n个结点共有2n个指针域(Lchild和Rchild) ，所以有n+1个空闲指针域未用。
可以利用这些空闲的指针域来寄存结点的直接先驱和直接后继信息。
对结点的指针域做以下规定：
◆ 若结点有左孩子，则Lchild指向其左孩子，否则，指向其直接先驱；
◆ 若结点有右孩子，则Rchild指向其右孩子，否则，指向其直接后继；
用这类结点结构构成的2叉树存储结构；叫做线索链表；指向结点先驱和后继的指针叫做线索；依照某种次序遍历，加上线索的2叉树称之为线索2叉树。
线索2叉树的结点结构与示例
typedef struct BiTreeNode
{ ElemType data;
struct BiTreeNode *Lchild , *Rchild ;
int Ltag , Rtag ;
}BiThrNode ;
如何在线索树中找结点的直接后继?以图 ，所示的中序线索树为例：
◆ 若树中结点的右链是线索（Rtag=1），则右链直接唆使了结点的直接后继，如结点G的直接后继是结点E。
◆ 若树中结点的右链是指针（ Rtag=0）。根据中序遍历的规律， Rtag=0的结点的直接后继是遍历其右子树时访问的第1个结点，即右子树中最左下位置的(叶子)结点。如结点C的直接后继：沿右指针找到右子树的根结点F，然后沿左链往下直到Ltag=1的结点即为C的直接后继结点H。
在后序遍历的线索树中找结点的直接后继比较复杂，可分以下3种情况：
若结点是2叉树的根结点：其直接后继为空；
若结点是其父结点的左孩子且其父结点没有右子树：直接后继为其父结点；
若结点是其父结点的左孩子且其父结点有右子树：直接后继是对其父结点的右子树按后序遍历的第1个结点。
2叉树的线索化指的是依照某种遍历次序使2叉树成为线索2叉树的进程。
线索化的进程就是在遍历进程中修改空指针使其指向直接先驱或直接后继的进程。
下面主要讨论按中序遍历次序线索化2叉树。
仿照线性表的存储结构，在2叉树的线索链表上也添加1个头结点head，头结点的指针域的安排是：
◆ Lchild域：指向2叉树的根结点；
◆ Rchild域：指向中序遍用时的最后1个结点；
◆ 2叉树中序序列中的第1个结点Lchild指针域和最后1个结点Rchild指针域均指向头结点head。
添加了头结点的线索2叉树，犹如为2叉树建立了1个双向线索链表，对1棵线索2叉树既可从头结点也可从最后1个结点开始按寻觅直接后继进行遍历。明显，这类遍历不需要堆栈。
#define MAX_NODE 50
typedef enmu{ Link , Thread} PointerTag ;
/* Link=0表示指针， Thread=1表示线索 */
typedef struct BiThrNode
{ ElemType data;
struct BiTreeNode *Lchild , *Rchild ;
PointerTag Ltag , Rtag ;
}BiThrNode, *BiThrTree;
ElemType Nil=‘#’; /*以#为空 */
Status CreateBiThrTree(BiThrTree *T)
{ ElemType ch;
scanf("%c",&ch);
if(h==Nil) *T=NULL;
else
{ *T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*T) return ERROR;
(*T)->data=ch; /* 生成根结点(前序) */
CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
if((*T)->lchild) (*T)->LTag=Link; /* 有左孩子 */
CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
if((*T)->rchild) (*T)->RTag=Link; /* 有右孩子 */
}
return OK;
}
BiThrNode *pre//全局变量，始终指向刚刚访问过的结点
void InThreading (BiThrNode *T)
{ if(T)
{ Inorder_Threading(T->lchild) /* 递归左子树线索化 */
if(!T->lchild) /* 没有左孩子 */
{ T->LTag=Thread; /* 先驱线索 */
T->lchild=pre; /* 左孩子指针指向先驱 */
}
if(!pre->rchild) /* 先驱没有右孩子 */
{ pre->RTag=Thread; /* 后继线索 */
pre->rchild=T; /* 先驱右孩子指针指向后继(当前结点T) */
}
pre=T; /* 保持pre指向T的先驱 */
Inorder_Threading(T->rchild); /* 递归右子树线索化 */
}
}
先驱结点的线索化：if(!T->lchild)表示如果某结点的左指针域为空，由于其先驱结点刚刚访问过，赋值给了pre，所以可将pre赋值给T->lchild，并修改T->LTag=Thread（即定义为1）以完成先驱结点的线索化；
后继结点的线索化：因此时后继结点还没有访问到，因此只能对它的先驱结点pre的右指针rchild做判断， if(!pre->rchild)表示如果先驱的右指针域为空，则T就是pre的后继，因而pre->rchild=T，并且设置pre->RTag=Thread，完成后继结点的线索化。
完成先驱和后继的判断后，要将当前结点T赋值给pre，以便于下次使用。
/* 中序遍历2叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrdhead, BiThrTree T)
{ * Thrdhead =(BiThrTree)malloc(sizeof(BiThrNode));
if(!* Thrdhead ) return ERROR;
(* Thrdhead )->LTag=Link; /* 建头结点 */
(* Thrdhead )->RTag=Thread;
(* Thrdhead )->rchild= NULL; //右指针此时为空
if(!T) (* Thrdhead )->lchild= * Thrdhead; //若2叉树空,则左指针回指
else
{
(* Thrdhead )->lchild=T; //非空，指向根节点
pre=(* Thrdhead );
InThreading(T); /* 中序遍历进行中序线索化 */
pre->rchild=* Thrdhead; //pre是中序遍历的最后1个结点
pre->RTag=Thread; /* 最后1个结点线索化 */
(* Thrdhead )->rchild=pre;
}
return OK;
}
线索2叉树的创建虽然比较复杂，但在线索2叉树中，由于有线索存在，在某些情况下可以方便地找到指定结点在某种遍历序列中的直接先驱或直接后继。
另外，在线索2叉树上进行某种遍历比在1般的2叉树上进行这类遍历要容易很多，不需要设置堆栈，且算法10分简洁。
/* 中序遍历2叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild; /* p指向根结点 */
while(p!=T) /* 空树或遍历结束时,p==T */
{ while(p->LTag==Link)
p=p->lchild; //当LTag==0时循环到中序序列第1个结点
visit(p->data);
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 访问后继结点 */
}
p=p->rchild;
}
return OK;
}
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
