线索二叉树

标签：pre 结点 前驱 二叉树 rchild 线索

线索二叉树的实现

内涵，一棵n个结点的树中一定会存在n+1个空指针域，将此指针域给利用起来，实现指向前驱或后继。

其线索二叉树，等于把一颗二叉树转化为一个双向链表。

对二叉树以某种次序遍历使其变为线索二叉树的过程被称为线索化，线索化的过程就是在遍历过程中修改空指针的过程。

存储结构：

typedef char TElemType;
typedef enum {Link，Thread} PointerTag;
typedef struct BiThread
{
    TElemType data;//数据域
    struct BiThrNode *lchild,*rchild;//指针域
    PointerTag LTag;//左标志
    PointerTag RTag;//右标志
}BiThrNode,*BiThrTree;

中序遍历线索化代码：

 1 BiThrTree pre;        //全局变量，始终指向刚刚访问的结点
 2 void InThreading(BiThrTree p)
 3 {
 4     if(p)
 5     {
 6         InThreading(p->lchild);    //递归左子树线索化
 7         if(!p->lchild)    //没有左孩子
 8         {
 9             p->LTag=Thread;//前驱线索
10             p->lchild=pre;//左子树指向前驱
11           }
12         if(!pre->rchild)//前驱没有右孩子
13         {
14             pre->RTag=Thread;　　　　　　//后继线索
15             pre->rchild=p;        //前驱右孩子指针指向后继（当前结点p）
16                                           //因为是中序遍历，前驱的右节点就是结点p的后继
17             }
18             pre=p;　　　　　　//保持pre指向p的前驱
19             InThreading(p->rchild);　　　　//进行递归右子树线索化
20 }

对线索二叉树遍历时，其实就等同于操作一个双向链表结构！

而且也可以添加一个头节点，最后形成，双向循环链表结构。

加头节点的遍历：

Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;　　　　　　
    p=T->lchild;　　　　//p指向根节点
    while(p!=T)　　　　　//空树或便利结束时，p==T
    {
        while(p->LTag=Link)　　　　//当LTag==0时循环到中序序列第一个结点
            p=p->lchild;
        printf("%c",p->data);　　　　//显示结点数据，可以更改为其他对结点的操作
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild;
            printf("%c",p->data);　　　　//访问后继结点
        }
        p=p->rchild;　　　　//p进至其右子树根
　　　　　　}
　　　　return OK;
}

如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择！

标签：pre,结点,前驱,二叉树,rchild,线索
From： https://www.cnblogs.com/abwork-space/p/17062868.html