04月
01

发表于 • 字数统计 3805 • 被 1,959 人看爆

线索二叉树

概念

n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

线索链表的结点结构

lchild ltag data rtag rchild

线索链表结构.png

例

线索链表例.png

二叉线索树画法

(1)首先将其序列列出来：中序序列：BDCAFHEG
(2)画出二叉树，并查看哪些结点缺少左右结点
(3)二叉树缺少的对照序列(该为中序序列)
(4)如从序列B开始：B没有左结点，则左节点为空，右节点指向D
  D的左结点指向B，右结点指向C；C的左结点指向D，右结点指向A

详情视频

线索链表的结点类型定义

typedef struct node{ 
    DataType data;
    int ltag，rtag;
    struct node *lchild,*rchild;
    
}BinThrNode;            //线索链表结点类型

typedef BinThrNode *BinThrTree;         //定义线索链表类型

二叉树线索化算法

算法思想
按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可.

  • (1)如果根结点的左孩子指针域为空，则将左线索标志域置1，同时给根结点加左线索(将前趋结点的指针赋给根结点的左指针域)。
  • (2)如果根结点的右孩子指针域为空，则将右线索标志域置l，同时给根结点加右线索(将后继结点的指针赋给根结点的右指针域)。
  • (3)将根结点指针赋给存放前趋结点指针的变量，以便当访问下一个结点时，此根结点作为前趋结点。

设pre指向前趋结点的指针，它始终指向刚刚访问过的结点，初值置空；设bt为指向当前正在访问的结点，显然，*pre是结点 *bt的前趋结点，*bt则是 *pre的后继结点，bt初始值指向二叉树的根结点

二叉链表加中序线索的算法

算法与中序遍历算法类似，只是将遍历算法中访问根结点*bt的操作改为在 *bt和中序前趋 *pre之间建立线索。
算法时间复杂度O(n)

算法描述

//对应于中序遍历中访问根节点
void InorderThread(BinThrTree bt)
{ 
    Static BinThrNode *pre=NULL;
    //定义指向前趋结点的指针pre(静态变量，只初始化1次)，保存刚访问过的结点
    if(bt !=NULL)                         //当二叉树为空时结束递归  
    {
        InorderThread(bt->lchild);        //左子树线索化
        if(bt->lchild==NULL) 
            bt->ltag=1;
        else
            bt->ltag=0;
        
        if(bt->rchild==NULL) 
            bt->rtag=1;
        else 
            bt->rtag=0;
        
        if(pre)
        {
            if(pre->rtag==1)
                pre->rchild=bt;         //给前趋结点加后继线索
            
            if(bt->ltag==1)
                bt->lchild=pre;         //给当前结点加前趋线索
        }
        pre=bt;                         //将刚访问过的当前结点置为前趋结点
        InorderThread(bt->rchild);      //右子树线索化
    }

}

二叉线索链表上的运算

在中序线素二叉树上查找某结点的后继结点

分析： 分两种情况
以下图为例
线索链表例.png

(1)若结点*p的rtag域值为1，则表明p->rchild为右线索，它直接指向结点 *p的中序后继结点。比如图(c)中，若p指向数据与值为"C"的结点，该结点的rtag域值为1(为0时指向右孩子)，那么它的中序后继结点就是p->rchild指向的结点，即数据域值为"A"的结点
(2)若结点 *p的rtag域值为0，则表明p->rchild指向右孩子结点，结点 *p的中序后继结点必是其右子树第一个中序遍历到的结点，因此从结点 *p的右孩子开始，沿左指针链向下查找，直到找到一个没有左孩子(即ltag为1)的结点为止，该结点是结点 *p的右子树中"最左下"的结点，它就是结点 *p的中序后继结点。如图(c)中，若p指向数据域值为"B"的结点，该结点的rtag域值为0，那么它的中序后继结点就是p->rchild指向结点的左孩子结点，即数据域为"D"的结点

算法描述：

BinThrNode *InorderNext(BinThrNode *p)
{
    //在中序线索二叉树上求结点*p的中序后继结点
    if(p->rtag==1)                      //rchild域为右线索
        return p->rchild;               //返回中序后继结点指针
    else {
        p=p->rchild;                    //从*p的右孩子开始
        while(p->ltag==O)
            p=p->lchild;                //沿左指针链向下查找
        
        return p;
    }
}

时间复杂度为O(h) h为二叉树的高度

线索二叉树的中序遍历算法

基本思想： 首先从根结点起沿左指针链向下查找，直到找到一个左线索标志为1的结点止，该结点的左指针域必为空，它就是整个中序序列中的第一个结点。访问该结点，然后就可以依次找结点的后继，直至中序后继为空时为止。

算法描述：

void TinorderThrTree(BinThrThrtree bt)
{ 
    BinThrNode *p;
    if(bt!=NULL)                    //二叉树不空
    {
        p=bt;                       //使p指向根结点
        while(p->ltag==O)           //查找出中序遍历的第一个结点
            p=p->lchild;
        
        do{
            printf("%c"，p->data);      //输出访问结点值
            p=InorderNext(p);           //调用前面的函数查找结点*p的中序后继
            
        }while(p!=NULL);                //当p为空时算法结束
    }

算法时间复杂度为O(n)

分享到：