线索二叉树

一、线索链表

保存二叉树的某种遍历序列： (1)如果二叉树不改变: 顺序存储(数组）

(2)如果二叉树改变：链式存储(链表)

存储遍历序列：假设二叉链表具有n个结点，则有n+1个空指针 将二叉链表中的空指针域利用起来，指向其前驱结点和后继结点 线索：将二叉链表中的空指针域指向其前驱结点和后继结点的指针被称为线索

线索化：使二叉链表中结点的空链表域存放其前驱或后继信息的过程被称为线索化

线索链表：加上线索的二叉链表称为线索链表（线索二叉树）

结点结构：

struct ThreadNode
{
    DataType data;
    ThreadNode *lchild,*rchild;
    int ltag,rtag;
};

二、线索二叉树

二叉树的遍历方式有4种，相应的线索二叉树也有四种遍历方式 (1)前序线索二叉树 (2)中序线索二叉树 (3)后序线索二叉树 (4)层序线索二叉树

中序线索二叉树

1.建立线索链表

实质上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或者后继的信息只有在遍历二叉树时才能得到

算法描述 1.建立二叉链表，将每个结点的左右标志置0

2.遍历二叉链表，建立线索: a.如果二叉链表p为空，则空操作返回 b.对p的左子树建立线索 c.对根结点P建立线索

(1).若没有左孩子，则为p加上前驱线索 (2).若pre没有右孩子，则pre加上 后继线索 (3).令pre指向刚刚访问的结点p

d.对p的右子树建立线索

// p为正在访问的结点，pre为刚访问的结点
void ThreadBiTree::inThread(ThreadNode *p)
{	
	static ThreadNode *pre = NULL;  // 注意pre的定义
    if(p==NULL)return;
    inThread(p->lchild); // 左子树线索化
    if(p->lchild==NULL)  //建立p的前驱结点
    {
        p->ltag = 1;
        p->lchild = pre;
    }
    if(pre!=NULL && pre->rchild == NULL) // 建立pre的后继结点
    {
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;
    inThread(p->rchild);
}

线索二叉表的作用：将树转换为线性表，将遍历的信息在首次遍历时线索化，则可以在需要时直接获得结点的前驱和后继

2.中序线索二叉链表查找后继

(1)如果结点p的右标志为1,则表明该结点的右指针是线索

(2)如果结点p的右标志为0,则表明该结点有右孩子。根据中序遍历的操作定义，它的后继结点应该是遍历其右子树时第一个访问的结点，即右子树中的最左下结点

ThreadNode* ThreadBiTree::next(ThreadNode *p)
{
    if(p->rtag == 1) //右标志为1，可直接得到后继结点
        q = p->rchild;
    else             // 右标志为0，则要查找右子树最下角的结点
    {
        q = p->rchild;
        while(q->ltag == 0)  //查找最左下结点位置
        {
            q = q->lchild;
        }
    }
    return q;
}

3.遍历中序线索链表

void ThreaBitree::inOrder()
{
    ThreadNode* p;
    if(root==NULL) return;
    p = root;
    while(p->ltag==0) // 查找中序遍历的第一个结点
    {
        p = p->lchild;
    }
    visit(p->data); // 一个结点
    while(p->rchild !=NULL)
    {
        p = next(p);
        visit(p->data);
    }
}