数据结构——线索二叉树

二叉树的遍历顺序

前序遍历：1、2、4、5、3、6

中序遍历：4、2、5、1、6、3

后序遍历：4、5、2、6、3、1

线索二叉树

利用二叉树链表的空指针实现线索二叉树。

线索化：

若无左子树，则将其左指针指向其前驱结点；
若无右子树，则将其右指针指向其后继结点；

先序线索二叉树

前序遍历：1、2、4、5、3、6

中序线索二叉树（较为常用）

中序遍历：4、2、5、1、6、3

中序遍历：第一个结点是最左侧结点，最后一个结点是最右边的结点。

前驱结点：

若左指针为线索，则其指向结点为前驱结点；
若左指针为左孩子，则其左子树的最右侧结点为前驱结点。

后继结点：

若右指针为线索，则其指向结点为后驱结点；
若右指针为右孩子，则其右子树的最左侧结点为后驱结点。

void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T!=NULL){
        InTread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

// 引用类型：需要对其进行修改
void InTread(ThreadTree &p,ThreadTree &pre){
    // 传入参数 线索二叉树根结点、对应节点前驱结点
    if(p!=NULL){
        // 判断根结点是否为空
        InThread(p->lchild,pre);
        // 线索化，递归调用线索化左子树：左子树根结点及前驱结点
        if(p->lchikd==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        InThread(p->rchild,pre);
    }
}

带有头结点的中序线索二叉树：

增加一个头结点

左指针指向根结点；
第一个遍历序列（4）左指针指向头结点；
头结点的右指针指向最后一个遍历序列（3）;
遍历序列的最后一个结点（3）的右指针指向头结点。

后序线索二叉树

后序遍历：4、5、2、6、3、1

线索二叉树结点结构——线索链表

增加两个标志位：

$标志域l(r)tag=\begin{cases} 0, & \text{$l(r)child$ 域指示结点的左（右）孩子}\\ 1, & \text{$l(r)child$ 域指示结点的前驱（后继）} \end{cases}$

typedef structure ThreadNode{
    ElemType data;
    structure ThreadNode *lchild, *rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

中序线索二叉树遍历

寻找第一个结点：

// 从根结点出发，循环找到最左侧的结点
ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag==0)
        p=p->lchild;
    return p;
}

找到后继结点：

ThreadNode *Nextnode(ThreadNode *p){
	if(p->rtag==0)
        // tag为0为孩子结点，需要找到它右子树最左侧结点为后继
        return Firstnode(p->rchild);
    else
        // tag为1为先做点，右指针就是后继结点
        return p->rchild;
}

循环调用寻找后继节点的函数：

void InOrder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}