详细图解二叉树线索化及其实现

为了更好的阅读体验你可以查看我的github原文

线索二叉树节点定义

图示

二叉树线索化的过程中，会把树中的空指针利用起来作为寻找当前节点前驱和后继的线索，这样就出现了一个问题，即线索和数中原有指向孩子节点的指针无法区分。上边的这种节点设计就是为了区分这两类指针。其中，ltag和rtag为标识域，它们的具体意义如下。

1. 如果ltag==0，表示lchild为指针，指向结点的左孩子；如果ltag==1，表示lchild为线索，指向结点的直接前驱。
2. 如果rtag==0，表示rchild为指针，指向结点的右孩子；如果rtag==1，表示rchild为线索，指向结点的直接后继。

中序遍历二叉树线索化步骤图解

因为考研书上说考中序遍历的频率比较高，其实弄懂了一个就容易理解其他的了。所以本文拿中序遍历举例。

原有的二叉树链表表示为

step0

1.先递归左子树

递归找到B，p指向B

step1

如果p的左子树为空，p->lchild=pre(这时pre为null)。

2. 向下遍历移动指针

这时p有右孩子，则将p移动到右孩子上，pre移动到p之前的位置

step2

如果p没有左孩子，p->lchild=pre

step2+

3. 根的左子树递归结束，p进入根节点

pre没有右孩子则pre->rchild=p

step3

之后pre=p,p=p->rchild

4.从C递归找左孩子，即E，此时p指向E

step4

此时p在e上，e没有左孩子，所以指向pre（即A）。之后，p指向e的右孩子即null，pre指向e。(记住p一指向下一个，pre就指向p之前的位置。)

5.C上右子树递归结束，p指向c

pre此时在e上，e没有右孩子，所以pre->right=p。

step5

6.中序遍历二叉线索树构建完成

step6

规律总结

算法看起来很复杂，其实抽象来看就是两个双向链表的节点的前驱后继指针的操作。

demo

算法实现

通过上面的规律，再结合遍历顺序进行递归操作。

// 定义二叉线索树节点
typedef struct TBTNode{
    char data;
    int ltag,rtag;
    struct TBTNode *lchild;
    struct TBTNode *rchild;
}TBTNode;

// 中序遍历二叉树线索化
void InThread(TBTNode *p,TBTNode *pre){
    if(p!=NULL){
        InThread(p->lchild,pre); // 递归左子树
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        p=p->rchild;
        InThread(p,pre);// 递归右子树
    }
}

关注我的订阅号获得计算机考研题目更加及时的推送~

wechat：那屋水泡