线索二叉树

一、线索二叉树的构造

#include <stdio.h>
//定义线索二叉树结点
typedef struct ThreadNode
{
    int data; //数据域存放二叉树数据
    ThreadNode * lchild,*rchild; //左右孩子
    int ltag,rtag; //左右孩子标志位
}ThreadNode,* ThreadTree;

ThreadNode * pre; //全局变量，当前结点的前驱结点

二、构造并中序线索化

//访问某一个树结点同时进行线索化
void Visit(ThreadNode * p)
{
    if(p->lchild==NULL)
    {
        p->lchild=pre;
        p->ltag=1;
    }
    if(pre!=NULl&&pre->rchild==NULL)
    {
        pre->rchild=p; //建立前驱结点的后继线索
        pre->rtag=1;
    }
    pre=p; //把pre置为当前结点，当下一次调用visit时访问的pre就是当前结点（下一次遍历的前驱）
}
//二叉树中序遍历（并调用Visit进行线索化）
void InThread(ThreadTree T)
{
    if（T！=NULL）
    {
     InThread(T->lchild);
     Visit(T);
     InThread(T->rchild);
    }
}

void CreateInThread(ThreadTree T)
{
    pre=NULL;
    if(T!=NULL)
    {
        InThread(T);
        if(pre->rchild==NULL) pre->rtag=1; //对最后一个结点进行特殊处理
    }  
}

三、构造并先序线索化（构造代码同上）

//二叉树先序遍历（并调用Visit进行线索化）
void InThread(ThreadTree T)
{
    if（T！=NULL）
    {
    Visit(T);
    if（T->LTag==0）InThread(T->lchild); //!!!注意此处的判断条件，因为先序遍历访问顺序是根左右，如果根线索化了，无论根有没有左孩子，lchild都有指向，因此必须加此判断条件，判断其到底有没有左孩子
    InThread(T->rchild);
    }
}

四、线索二叉树的遍历

（1）中序遍历

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

//找到某个结点的后继节点
ThreadNode * NextNode(ThreadNode * p)
{
    if(p->rtag==1) return p->rchild;
    else if(p->rchild==0) return FirstNode(p->rchild); //返回右子树最左下的那个结点
}

void Inorder(ThreadTree * T)
{
    for(ThreadNode * p=FirstNode(T)；p!=NULL；p=NextNode(p)) //先找到第一个结点，然后不断的找其后继
        visit(p);
}

（2）逆向中序遍历：从最后一个结点开始不断遍历其前驱即可。