线索二叉树

介绍

在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。 对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

优势

(1)利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。 (2)任意一个结点都能直接找到它的前驱和后继结点。

不足

(1)结点的插入和删除麻烦，且速度也较慢。 (2)线索子树不能共用。

算法实现

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。

线索二叉树的递归算法

void inThread (ThreadTree &p,ThreadTree &pre)
{
    if(P!=NULL){
    inTread(p->lchild,pre);
    if(p->lchild==NULL)
    p->lchild=pre;
    p->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL)
    {
        pre->rchild=p;
        pre->rtag=1;
    }
    pre=p;
    inTread(p->rchild,pre);
}

建立中序线索二叉树

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