线索二叉树¶

Tip

本节主要以选择题的形式考察，对于线索二叉树来说，遍历序列的第一个结点前驱指向NULL,最后一个结点的后继指向NULL；其余结点没有左孩子的话lchild指向前驱结点，没有右孩子的话线索rchild指向后继结点；这里的前驱后继取决于这是哪一种线索二叉树，如果是先序线索二叉树，其前驱和后继就是先序序列中的前驱和后继，如果是中序或者后序的话就按找照对应规则找。

之前在二叉树的链式存储结构中提到，传统的二叉树结构只能体现一种父子关系，不能直接得到某节点的前驱和后继，每次都要设置一个p和pre指针从根结点开始遍历。并且，在含有n个结点的二叉树中，有n+1个空指针，为此，我们可以利用这些空指针来实现线索二叉树，从而加快查找某节点的前驱和后继的速度。

规定：若无左子树，令lchild指向其前驱节点；若无右子树，令rchild指向其后继结点。为了区分指针指的是孩子节点还是前驱或后继，还要增加两个标志域标识。

其中，标志域的含义如下：

ltag == 0时指向左孩子; ltag == 1时指向前驱
rtag == 0时指向右孩子; rtag == 1时指向后继

因此，线索二叉树的结构体定义为

typedef struct ThreadNode {
    int data;    //数据域
    struct ThreadNode* lchild,*rchild;    //左、右孩子指针
    int ltag,rtag;     //左、右线索指针
}ThreadNode,*ThreadTree;

这样的指针称之为线索，加上线索的二叉链表称之为线索链表，相应的二叉树就称之为线索二叉树。

中序线索二叉树的构造¶

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程.线索二叉树类似于一个非循环的双向链表。

构造过程：设置两个指针，p和pre，pre用于指向刚刚访问过的结点，p用于指向正在访问的结点，即pre指向的是p的前驱。在中序遍历的过程中，如果p没有左孩子，则将其左孩子指针指向pre；如果pre没有右孩子，则将其右孩子指针指向p；

void InThread(ThreadNode* p,ThreadNode *&pre){ 
    if(p != NULL) {     
        InThread(p->lchild,pre);   //递归线索化左子树
        if(p->lchild == NULL) {   //如果p没有左孩子，即左孩子指针为空，建立前驱线索
            p->lchild = pre;    //将其指向前驱结点；
            p->ltag = 1;   //修改标识，表示线索化；
        }else{ 
            p -> ltag = 0;   
        }
        if(pre!=NULL && pre -> rchild == NULL) {   //如果pre没有右孩子，即右孩子指向空；
            pre -> rchild = p;   //将其右孩子指针指向p；
            pre -> rtag = 1;   //修改标识；
        }else if (pre != NULL) { //首次访问时 pre 为空，不能解引用空指针
            pre->rtag = 0;
        }
        pre = p;   //更新遍历结点；表示当前结点成为刚刚访问过的结点；
        InThread(p->rchild,pre);   //递归线索化右子树；
    }
}

void CreateInThread(ThreadTree root) {   
    ThreadNode *pre = NULL;   
    if(root) {      //非空二叉树线索化；
        InThread(root,pre);   //线索化二叉树；
        pre -> rchild = NULL;   //处理遍历的最后一个结点，将其后继指向空；
        pre -> rtag = 1;
    }
}

类似于带头结点的链表，线索二叉树也可以带头结点，将该头结点的lchild指向二叉树的根节点，其rchild执行中序遍历最后一个访问的结点；再令中序遍历的第一个结点的lchild指向该头结点，最后一个结点的rchild指向该头结点。这样的话，相当于为该二叉树建立了一个双向线索链表，从而方便从前往后或者从后往前对该线索二叉树遍历。

ThreadTree CreateInThread(ThreadTree root) { 
    ThreadNode *head = new ThreadNode();
    head->ltag = 0;   //预设指向root;
    head->rtag = 1;   //指向后继，即遍历序列最后一个节点；
    head -> rchild = head;  //先初始化右指针指向自己；
    ThreadNode *pre = NULL;   
    if(root) {      //非空二叉树线索化；
        head -> lchild = root;   //头结点的lchild指向二叉树的根节点  
        pre = head;
        InThread(root,pre);   //线索化二叉树；
        head -> rtag = 1;     //头结点的右指针始终是后继线索，避免被通用线索化过程改为孩子标志
        pre -> rchild = head;   //最后一个遍历到的结点后继指向头节点head；
        pre -> rtag = 1;
        head -> rchild = pre;   //头结点的后继应指向最后一个遍历到的结点，不能覆盖指向根的 lchild；
    }else{
        head -> lchild = head;  //树为空的话，左指针指向自己；
    }
    return head;
}

中序线索二叉树的遍历¶

中序线索二叉树中找结点`p`的后继¶

若p的rtag = 1,则该结点的后继就是p->rchild;若rtag = 0,则该结点的后继就是其右子树中第一个被访问到的结点（右子树中最左下的结点）

//找到以p为根的子树中，第一个被中序遍历访问到的结点；
ThreadNode *FirstNode(ThreadNode *p) {
    if (p == NULL) return NULL; //空树时不能直接访问 p->ltag
    //循环找到最左下结点（不一定是叶结点）
    while(p -> ltag == 0) {
        p = p -> lchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的后继结点；
ThreadNode *NextNode(ThreadNode* p){
    if(p->rtag == 0) {   //表示p结点有右孩子；
        return FirstNode(p->rchild);  //则其后继为其右子树的最左下结点；
    }else{      //rtag == 1,表明p结点没有右孩子，其右孩子指针指向其后继；
        return p -> rchild;   //直接返回后继结点；
    }
}

//对中序线索二叉树进行中序遍历(利用线索化实现的非递归，空间复杂度为O(1));
void Inorder(ThreadNode* root){
    for(ThreadNode *p = FirstNode(root);p!=NULL;p = NextNode(p))
        visit(p);
}

中序线索二叉树中找结点`p`的前驱¶

若p的ltag = 1,则该结点的前驱就是p->lchild;若ltag = 0,则该结点的前驱就是其左子树中最后一个被访问到的结点（左子树中最靠近右下的结点）

//找到以p为根的子树中，最后一个被中序遍历访问到的结点；
ThreadNode *LastNode(ThreadNode *p) { 
    if (p == NULL) return NULL;       
    //循环找到最右下结点（不一定是叶结点）
    while(p -> rtag == 0) {
        p = p -> rchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的前驱结点；
ThreadNode *PreNode(ThreadNode* p){
    if(p->ltag == 0) {   //表示p结点有左孩子；
        return LastNode(p->lchild); 
    }else{      //ltag==1,表明p结点没有左孩子，其左孩子指针指向其前驱；
        return p -> lchild; //直接返回前驱结点；
    }
}

//对中序线索二叉树进行逆向中序遍历
void Revorder(ThreadNode* root){
    for(ThreadNode *p = LastNode(root);p!=NULL;p = PreNode(p))
        visit(p);
}

先序和后序线索二叉树¶

建立先序和后序线索二叉树的代码与上述建立中序线索二叉树的代码类似，只需变动线索化改造的代码段和调用线索化左右子树递归函数的位置即可.

//先序线索化
void PreThread(ThreadNode* p,ThreadNode *&pre){ 
    if(p != NULL) {     
        if(p->lchild == NULL) {   //如果p没有左孩子，建立前驱线索
            p->lchild = pre;    //将其指向前驱结点；
            p->ltag = 1;   //修改标识，表示线索化；
        }else{ 
            p -> ltag = 0;   
        }
        if(pre!=NULL && pre -> rchild == NULL) {   //如果pre没有右孩子，则建立前驱结点的后继线索
            pre -> rchild = p;   //将其右孩子指针指向p；
            pre -> rtag = 1;   //修改标识；
        }else if (pre != NULL) { 
            pre->rtag = 0;
        }
        pre = p;   //更新遍历结点；表示当前结点成为刚刚访问过的结点；
        if(p->ltag == 0){
            PreThread(p->lchild,pre);   //递归线索化左子树；
        }
        if(p->rtag == 0){   //必须判断后再递归，否则会陷入死循环，王道课件代码没加，是有问题的
            PreThread(p->rchild,pre);   //递归线索化右子树；
        }

    }
}

void CreatePreThread(ThreadTree root) {   
    ThreadNode *pre = NULL;   
    if(root) {      //非空二叉树线索化；
        PreThread(root,pre);   //线索化二叉树；
        if(pre -> rchild == NULL)    //处理遍历的最后一个结点；
            pre -> rtag = 1;
    }
}

//后序线索化
void PostThread(ThreadNode* p,ThreadNode *&pre){ 
    if(p != NULL) {   
        PostThread(p->lchild,pre);   //递归线索化左子树；       
        PostThread(p->rchild,pre);   //递归线索化右子树；
        if(p->lchild == NULL) {   //如果p没有左孩子，建立前驱线索
            p->lchild = pre;    //将其指向前驱结点；
            p->ltag = 1;   //修改标识，表示线索化；
        }else{ 
            p -> ltag = 0;   
        }
        if(pre!=NULL && pre -> rchild == NULL) {   //如果pre没有右孩子，则建立前驱结点的后继线索
            pre -> rchild = p;   //将其右孩子指针指向p；
            pre -> rtag = 1;   //修改标识；
        }else if (pre != NULL) { 
            pre->rtag = 0;
        }
        pre = p;   //更新遍历结点；表示当前结点成为刚刚访问过的结点；       
    }
}

void CreatePostThread(ThreadTree root) {   
    ThreadNode *pre = NULL;   
    if(root) {      //非空二叉树线索化；
        PostThread(root,pre);   //线索化二叉树；
        if(pre -> rchild == NULL)    //处理遍历的最后一个结点；
            pre -> rtag = 1;
    }
}

先序线索二叉树找指定节点p的先序后继¶

Note

如果有左孩子，则左孩子就是其后继，如果无左孩子但是有右孩子，则右孩子为其后继；如果p是叶节点，则右链域指向的就是其后继；

先序线索二叉树找指定节点p的先序前驱¶

Note

若p->ltag == 1,则pre = p -> lchild;

若p->ltag == 0,由于先序遍历的遍历顺序是根左右，因此其左右孩子都只能是p结点的后继而不可能是前驱，所以此时只能从头开始找才能找到p的前驱；

或者可以在结构体中设置一个父节点指针，将其变为三叉链表，那样的话，找p结点的前驱有以下四种情况；

1. 如果能找到p的父节点，且p是左孩子	2. 如果能找到p的父节点，且p是右孩子，其左兄弟为空	3. 如果能找到p的父节点，且p是右孩子，其左兄弟非空	4. 如果p是根节点

p的父节点即为其前驱	p的父节点即为其前驱	p的前驱为左兄弟子树中最后一个被先序遍历的结点	则p没有先序前驱

后序线索二叉树找指定节点p的后序前驱¶

Note

若p->ltag == 1,则pre = p -> lchild;

若p->ltag == 0,则p必有左孩子；分情况讨论：

若p有右孩子	若p没有右孩子，那么肯定有且仅有左孩子
后序遍历---> 左右根左（左右根）根	后序遍历---> 左根（左右根）根
则后序前驱为右孩子	后序前驱为左孩子

后序线索二叉树找指定节点p的后序后继¶

Warning

若p->rtag == 1,则next = p -> rchild

后序线索树遍历最后访问根结点，若从右孩子返回访问双亲结点，那么因结点x的右孩子不一定是空的(导致右指针无法当作一个线索)，因此通过指针便无法遍历整棵树。所以说后序线索二叉树的遍历仍然需要栈

若p->rtag == 0,则p必有右孩子，但是后序遍历中，左右子树中的结点只可能是根节点的前驱，不可能是后继，除非从根节点开始遍历，或者和上面一样采用三叉链表；分情况讨论：

如果能找到p的父节点，且p是右孩子	如果能找到p的父节点，且p是左孩子，其右兄弟为空	如果能找到p的父节点，且p是左孩子，其右兄弟非空	如果p是根节点
后序遍历---> 左右根左（左右根）根	后序遍历---> 左根（左右根）根	左右根
p的父节点即为其后继	p的父节点即为其后继	p的后继为右兄弟子树中第一个被后序遍历的结点	p没有后继

总结：

	中序线索二叉树	先序线索二叉树	后序线索二叉树
找前驱
找后继

真题演练¶

【2010-03】下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）

解析

这棵树的后序遍历是

后序线索化时，空左指针指向后序前驱，空右指针指向后序后继：

b 的左指针为空，b 的前驱是 d，所以左线索指向 d；
c 是叶结点，前驱是 b、后继是 a，所以 c 的左右线索分别指向 b、a；
d 是第一个后序结点，左线索指向 NULL；d 的后继是 b，所以右线索指向 b；
a 的左右指针均为真实孩子指针，不建立线索。

这与题图中的 D 一致。

答案：D

【2013-05】若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y 。则 X 的右线索指的是（）。

A. X 的父结点

B. 以 Y 为根的子树的最左下结点

C. X 的左兄弟结点 Y

D. 以 Y 为根的子树的最右下结点

解析

X 存在左兄弟 Y，说明 X 是父结点的右孩子。

后序遍历顺序是

遍历完左兄弟 Y 所在的左子树后，会遍历右子树 X。X 是叶结点，访问 X 后，父结点的两个子树都已处理完，因此下一个访问的结点就是 X 的父结点。

叶结点 X 的右指针为空，在后序线索化中应改为指向其后序后继，即父结点。

答案：A

【2014-04】若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是（）。

A. e、c

B. e、a

C. d、c

D. b、a

解析

中序遍历按“左子树—根—右子树”进行：

d 的中序序列为 d、e；
b 的左子树之后访问 b，再访问右孩子 x；
最后访问 a、c。

所以完整中序序列为

x 是叶结点，左右指针都为空：

x 的中序前驱是紧邻它之前的 b，所以左线索指向 b；
x 的中序后继是紧邻它之后的 a，所以右线索指向 a。

答案：D

模拟预测题¶

对下列二叉树进行先序线索化：

结点 g 的左、右线索分别指向（）。

A. d、c\ B. e、c\ C. b、e\ D. e、NULL

解析

答案：B

对下列二叉树进行后序线索化：

结点 c 的 (ltag, rtag) 以及左右指针指向分别是（）。

A. (1,1)，f、a\ B. (0,1)，f、a\ C. (0,1)，a、NULL\ D. (1,0)，f、c

解析

答案：B

在中序线索二叉树中，结点 x 满足：

ltag=1，left=p
rtag=0，right=q

下列说法一定正确的是（）。

A. p 是 x 的父结点，q 是 x 的后继\ B. p 是 x 的前驱，q 是 x 的后继\ C. p 是 x 的前驱，q 是 x 的右孩子\ D. p 是 x 的左孩子，q 是 x 的父结点

ltag=1 表示左线索，rtag=0 表示右孩子。

解析

答案：C

ltag = 1 ⇒ left 域存的是线索 ⇒ p 是 x 的中序前驱（不是父、不是左孩子）；
rtag = 0 ⇒ right 域存的是真实右孩子 ⇒ q 是 x 的右孩子（不是后继、不是父）。

故"p 是前驱、q 是右孩子"，选 C。

一棵二叉树的先序序列和中序序列分别为：

先序：a，b，d，e，c，f，g
中序：d，b，e，a，f，c，g

若对其进行后序线索化，结点 e 的左、右线索分别指向（）。

A. b、d\ B. NULL、b\ C. d、a\ D. d、b

解析

答案：D

若 X 是先序线索二叉树中的非根叶结点，且 X 存在左兄弟结点 Y，则 X 的左线索指向的是（）。

A. X 的父结点\ B. X 的左兄弟结点 Y\ C. 以 Y 为根的子树的先序最后一个结点\ D. 以 Y 为根的子树的先序第一个结点

解析

答案：C

若 X 是后序线索二叉树中的叶结点，且 X 是其父结点 p 的左孩子，同时 p 存在右子树。则 X 的右线索（后序后继）指向（）。

A. 父结点 p B. p 的右孩子 C. 以 p 的右孩子为根的子树中，后序遍历的第一个结点（即从 p 的右孩子起，有左走左、无左走右，直至叶结点） D. 以 p 的右孩子为根的子树中最右下的结点

解析

答案：C

线索二叉树¶

中序线索二叉树的构造¶

中序线索二叉树的遍历¶

中序线索二叉树中找结点p的后继¶

中序线索二叉树中找结点p的前驱¶

先序和后序线索二叉树¶

先序线索二叉树找指定节点p的先序后继¶

先序线索二叉树找指定节点p的先序前驱¶

后序线索二叉树找指定节点p的后序前驱¶

后序线索二叉树找指定节点p的后序后继¶

真题演练¶

模拟预测题¶

中序线索二叉树中找结点`p`的后继¶

中序线索二叉树中找结点`p`的前驱¶