4.3 线索二叉树

4.3.1 线索二叉树定义

背景：为解决遍历只能从根结点开始这个问题，因为普通二叉树找前驱和后继很麻烦

线索二叉树在二叉树的结点上加上线索的二叉树。

4.3.2 线索二叉树的存储结构

由二叉树的链式存储改进而来

二叉树的类型表述

typedef struct TreeNode{
	Elemtype data;                   //数据域
	struct BiTNode *lchide, *rchild; //左、右孩子指针
}BiTNode, *BiTree;

线索二叉树的类型表述

typedef struct TreeNode{
	Elemtype data;                   //数据域
	struct BiTNode *lchide, *rchild; //左、右孩子指针
    int ltag, rtag;                  //左、右线索标志
}ThreadNode, *ThreadTree;

• tag==0：表示指针指向孩子
• tag==1：表示指针指向线索

4.3.3 线索二叉树的分类

中序线索二叉树、先序线索二叉树、后续线索二叉树

4.3.4 二叉树线索化

对二叉树进行线索化：对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程。

中序线索化

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//中序线索化二叉树T(三种一样，只是调用线索化函数不同)
void CreateThread(ThreadTree T){
    pre = NULL;              //pre初始为NULL
    if(T != NULL){           //非空二叉树才能线索化
        InTread(T);          //中序线索化二叉树
        if(pre->rchild == NULL){
            pre->rtag = 1;   //处理遍历的最后一个结点
        }
    }
}

//中序遍历二叉树，一边遍历，一边线索化
void InOrder(ThreadTree T){
    if(T!=NULL){
        InOrder(T->lchild);	//递归遍历左子树
        visit(T);               //访问根结点
        InOrder(T->rchild);	//递归遍历右子树
    }
}

//访问结点，顺便线索化（三种一样）
void visit(TheadNode *q){
    if(q->lchild == NULL){//左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild = q; //建立前驱结点的后继线索
        pre->rtage = 1;
    }
    pre = q;
}

先序线索化

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//先序线索化二叉树T(三种一样，只是调用线索化函数不同)
void CreateThread(ThreadTree T){
    pre = NULL;              //pre初始为NULL
    if(T != NULL){           //非空二叉树才能线索化
        PreTread(T);         //先序线索化二叉树
        if(pre->rchild == NULL){
            pre->rtag = 1;   //处理遍历的最后一个结点
        }
    }
}

//中序遍历二叉树，一边遍历，一边线索化
void PreOrder(ThreadTree T){
    if(T!=NULL){
        visit(T);               //访问根结点
        if(T->ltag == 0)        //lchild不是前驱线索，是线索还遍历则无限循环
            InOrder(T->lchild);	//递归遍历左子树
        InOrder(T->rchild);	    //递归遍历右子树
    }
}

//访问结点，顺便线索化（三种一样）
void visit(TheadNode *q){
    if(q->lchild == NULL){//左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild = q; //建立前驱结点的后继线索
        pre->rtage = 1;
    }
    pre = q;
}

后续线索化

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

//后序线索化二叉树T(三种一样，只是调用线索化函数不同)
void CreateThread(ThreadTree T){
    pre = NULL;              //pre初始为NULL
    if(T != NULL){           //非空二叉树才能线索化
        PostTread(T);        //后序线索化二叉树
        if(pre->rchild == NULL){
            pre->rtag = 1;   //处理遍历的最后一个结点
        }
    }
}

//中序遍历二叉树，一边遍历，一边线索化
void PostOrder(ThreadTree T){
    if(T!=NULL){
        InOrder(T->lchild);	    //递归遍历左子树
        InOrder(T->rchild);	    //递归遍历右子树
        visit(T);               //访问根结点
    }
}

//访问结点，顺便线索化（三种一样）
void visit(TheadNode *q){
    if(q->lchild == NULL){//左子树为空，建立前驱线索
        q->lchild = pre;
        q->ltag = 1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild = q; //建立前驱结点的后继线索
        pre->rtage = 1;
    }
    pre = q;
}

4.3.5 线索二叉树找前驱和后继

中序线索二叉树找中序后继

在中序线索二叉树中找指定结点*p的中序后继next

算法思想：

(1)若p->rtag == 1，则next为后继线索，即next = p->rchild。

(2)若p->rtag == 0，则p必有右孩子，next为p的右子树中最左下结点。

//找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点(不一定是叶子结点)
    while(p->ltag == 0) p = p->lchild;
    return p;
}

//在中序线索二叉树中找到结点p的后继结点
TheadNode *Nextnode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag == 0) return Fistnode(p->rchild);
    else return p->rchild;  //rtag=1直接返回后继线索
}

应用：中序线索二叉树的中序遍历

空间复杂度=O(1)

//对中序线索二又树进行中序遍历（利用线索实现的非递算法）
void Inorder(ThreadNode *T){
    for (ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))
		visit (p);
}

中序线索二叉树找中序前驱

在中序线索二叉树中找指定结点*p的中序前驱pre

算法思想：

(1)若p->rtag == 1，则pre为前驱线索，即pre = p->lchild。

(2)若p->rtag == 0，则p必有左孩子，pre为p的左子树中最右下结点。

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

//在中序线索二叉树中找到结点p的前驱结点
TheadNode *Prenode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag == 0) return Lastnode(p->lchild);
    else return p->lchild;  //rtag=1直接返回前驱线索
}

应用：中序线索二叉树的逆向中序遍历

空间复杂度=O(1)

//对中序线索二又树进行逆向中序遍历（利用线索实现的非递算法）
void Inorder(ThreadNode *T){
    for (ThreadNode *p=Lastnode(T); p!=NULL; p=Prenode(p))
		visit (p);
}

先序线索二叉树找先序后继

在先序线索二叉树中找指定结点*p的先序后继next

先序遍历：根左右。

算法思想：

(1)若p->rtag == 1，则pre为前驱线索，即next = p->rchild。

(2)若p->rtag == 0，则

①若p有左孩子，则next为左孩子

②若p没有左孩子，则next为右孩子

先序线索二叉树找先序前驱

在先序线索二叉树中找指定结点*p的先序前驱pre

由于先序遍历：根左右。p结点的左右子树中的结点只能是根的后继，不可能是前驱，因此无法找前驱

解决：改用三叉链表，三个指针：指向父结点、左孩子结点和右孩子结点

算法思想：

(1)若p->rtag == 1，则pre为前驱线索，即pre = p->lchild。

(2)若p->rtag == 0，则

​ ①若能找到p的父结点且p是左孩子，则pre为父结点

​ ②若能找到p的父结点且p是右孩子，其左兄弟为空，则pre为父结点

​ ②若能找到p的父结点且p是右孩子，其左兄弟为非空，则pre为左兄弟子树中最后一个被先序遍历的结点。

后序线索二叉树找后序后继

在后序线索二叉树中找指定结点*p的后序后继next

由于后序遍历：左右根。p结点的左右子树中的结点只能是根的后前驱，不可能是后继，因此`无法找前后继

解决：改用三叉链表，三个指针：指向父结点、左孩子结点和右孩子结点

算法思想：

(1)若p->rtag == 1，则next为后继线索，即next = p->rchild。

(2)若p->rtag == 0，则

​ ①若能找到p的父结点且p是右孩子，则next为父结点

​ ②若能找到p的父结点且p是左孩子，其右兄弟为空，则next为父结点

​ ②若能找到p的父结点且p是左孩子，其右兄弟为非空，则next为左兄弟子树中第一个被后续序遍历的结点。

后序线索二叉树找后序前驱

在后序线索二叉树中找指定结点*p的后序前驱pre

先序遍历：左右根。

算法思想：

(1)若p->rtag == 1，则pre为前驱线索，即pre = p->lchild。

(2)若p->rtag == 0，则

①若p有右孩子，则pre为右孩子

②若p没有右孩子，则pre为左孩子