数据结构之树（2)

摘要：本篇主要讲线索二叉树，灰常重要！

一、线索二叉树

不知道树的根节点时，给出指定结点，无法直接找到其前驱，除非用快慢指针进行记录。

因此，引出线索二叉树记录前驱后继。

n个结点的二叉树，有n+1个空链域，可用来记录前驱、后继的信息->线索化

前驱线索：左孩子指针充当  后继线索：右孩子指针充当

struct TreeNode{
    int data;
    struct TreeNode*lchild, *rchild;
    int ltag ,rtag;//左右线索标志，tag=0表示指针指向孩子，tag=1表示指向线索
}

二、二叉树线索化

中序

void InThread(TreeNode* root)
{
    if(root)
    {
        InThread(root->lchild);
        visit(root);
        InThread(root->rchild);
    }
}

void visit(TreeNode* root)
{
    if(root->lchild == nullptr)
    { root->lchild=pre; root->ltag=1;}
    if(pre!=nullptr && pre->rchild == nullptr)
    { pre->rchild=root; pre->rtag=1;}
    pre=root;
}

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

//中序线索化二叉树
void CreateInThread(TreeNode* root)
{
    pre=nullptr;
    if(root)
    {
        InThread(root);
        if(pre->rchild == nullptr)pre->rtag=1;
    }
}

先序：注意当Itag==0时，才能对左子树先序线索化

原因：当判断左子树为空时，左子树的左指针指向前驱结点，又因为接下来访问的结点是当前结点的左孩子（根左右），而左指针此时不为空，导致出错。

void PreThread(TreeNode* root){
    if(root){
    visit(root);//先处理根节点
    if (root->ltag ==0 )PreThread(root->lchild);
    PreThread(root->rchild);
    }
}

三、找前驱后继

1、找到指定结点的中序后继

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

若p->rtag==0,next为p的右子树中最左下结点

画图就明白

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

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

对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）（空间复杂度O（1））

void Inorder(ThreadNode T){
for(ThreadNode *p=FirstNode(T);p!=NULL;p=Nextnode(p))//p=Nextnode(p)很方便地找到后继
    visit(p);
}

2、找到指定结点的中序前驱

若p->ltag==1 next为p->lchild

若p->ltag==0 左子树最右边的结点

//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    //循环找到最右下结点（不一定时叶节点）
    while(p->rtag==0)p=p->rchild;
    return p;
}
//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    //左子树最右下结点
    if(p->ltag==0) return Lastnode(p->lchild);
    else return p->lchild;//ltag==1直接返回前驱线索
}

对中序线索二叉树进行逆向中序遍历

void RevInorder(ThreadNode *T){
    for (ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))
    visit(p);
}

附：

先序后继

p->rtag==0,则next为左孩子（左子树第一个被访问的结点）

根   左              右

根（根 左 右） 右

p->rtag==1（没有左孩子）,则next=p->rchild

先序前驱

改用三叉链表可以找到父结点

1、如果能找到p的父结点且p是左孩子，p的父结点即为前驱

2、如果能找到p的父结点，且p是右孩子，其左兄弟为空，p的父结点为前驱

3、如果能找到p的父结点，且P是右孩子，其左兄弟非空，p的前驱为做兄弟子树中最后一个被先序遍历的结点

4、如果p是根节点，则p没有先序前驱