| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 680 人关注过本帖
标题:线索二叉树基本操作详解
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
收藏
 问题点数:0 回复次数:0 
线索二叉树基本操作详解
线索二叉树基本操作详解
巧若拙(欢迎转载,但请注明出处:http://blog.

    遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列,得到二叉树中结点的先序,中序或后序序列。这实际上是对一个非线性结构进行线性化操作,使每个结点(除第一个和最后一个外)在这些线性序列中有且仅有一个直接前驱和直接后继。但是,当以二叉链表作为存储结构时,只能找到结点的左,右孩子的信息,而不能直接得到结点在任一序列中的前驱和后继信息,这种信息只能在遍历的动态过程中才能得到。
    因为在有n个结点的二叉链表中必定存在n+1个空链域,故可以利用这些空链域来存放结点的前驱和后继信息。
    试做如下规定:若结点有左子树,则其lchild域指示其左孩子,否则令lchild域指示其前驱;若结点有右子树,则其rchild域指示其右孩子,否则令rchild域指示其后继。为了避免混淆,需要改变结点结构,增加两个标志域:LTag,RTag。
    其中:LTag = 0,lchild域指示其左孩子;  LTag = 1,lchild域指示其前驱。
          RTag = 0,rchild域指示其右孩子;  RTag = 1,rchild域指示其后继。
    以这种结点组成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱和后继的指针,叫做线索。加上线索的二叉树叫做线索二叉树。对二叉树以某种次序遍历使其变成线索二叉树的过程叫做线索化。
    在线索二叉树上进行遍历,只要先找到序列中的第一个结点,然后依次找结点后继直到其后继为空为止;当然也可以找结点的前驱,进行逆序遍历。
    求各种次序线索树非叶子结点的前驱和后继的方法:
    前序线索树非叶子结点p的前驱:p的双亲结点;
    前序线索树非叶子结点p的后继:若p有左孩子,则后继为其左孩子,否则后继是其右孩子。
    后序线索树非叶子结点p的前驱:若p有右孩子,则后继为其右孩子;否则后继是其左孩子。
    后序线索树非叶子结点p的后继:若p为根结点,则其后继为空;若p为其双亲结点的右孩子,或p为左孩子且其双亲结点无右孩子,则p的后继为其双亲结点;
若p为左孩子,且其双亲结点有右孩子,则其后继为双亲结点右子树的第一个结点(最左边结点)。
    中序线索树非叶子结点p的前驱:左子树的最后一个结点(最右边的结点)。
    中序线索树非叶子结点p的后继:右子树的第一个结点(最左边结点)。
    前序线索树的后继很好找,但前驱是双亲结点,不便查找;虽然中序线索树前驱和后继都不是直接指向,但不需要求双亲,查找还是比较方便的;后序线索树的前驱很好找,但是后继需要分类讨论,情况复杂,而且需要求双亲。综合考虑,中序线索树是最佳的选择。
    为了方便起见,我们仿照线性表的存储结构,在二叉树的线索链表上也添加一个头结点,并令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;反之,令二叉树中序序列的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。这好比为二叉树建立了一个双向线索链表,既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历。
    我们先来分析如何将一颗普通二叉树改造成线索二叉树。因为普通二叉树没有头结点,故我们需要先创建一个头结点,然后对原二叉树做中序线索化处理。
/*
函数名称:InOrderThreading
函数功能:创建头结点,并将二叉树改造成中序线索树
输入变量:BiThrTree T:指向原二叉树根结点的指针
输出变量:BiThrTree:指向中序线索树头结点的指针
*/
BiThrTree InOrderThreading(BiThrTree T)
{
    BiThrTree Thrt, pre;
    Thrt = (BiThrTree)malloc(sizeof(BiThrNode));  //建立头结点
    if (!Thrt)
    {
        printf("Out of space!");
        exit(0);
    }
    Thrt->LTag = Link;
    Thrt->RTag = Thread;
    Thrt->rchild = Thrt; //右指针回指
   
    if (! T)//若二叉树为空,则左指针回指
    {
        Thrt->lchild = Thrt;
    }
    else
    {
        Thrt->lchild = T;
        pre = Thrt;
        InThreading_2(&T, &pre);//中序线索化

        pre->rchild = Thrt; //最后一个结点线索化,此时pre指向最后一个结点
        pre->RTag = Thread;
        Thrt->rchild = pre;
    }   
   
    return Thrt;
}
    中序线索化二叉树和中序遍历二叉树算法非常相似,也有递归和非递归有两种算法。代码如下。
/*
函数名称:InThreading_1
函数功能:中序遍历二叉树,并将其中序线索化(递归算法)
输入变量:BiThrTree *p:指向二叉树当前结点指针的指针
          BiThrTree *pre:指向二叉树树当前结点的前驱结点指针的指针
输出变量:无
*/
void InThreading_1(BiThrTree *p, BiThrTree *pre)
{
    if (*p != NULL)
    {
        InThreading(&(*p)->lchild, pre); //左子树线索化
        
        if ((*p)->lchild == NULL) //若当前结点的左子树为空,则建立前驱线索
        {
            (*p)->LTag = Thread;
            (*p)->lchild = (*pre);
        }
        else
        {
            (*p)->LTag = Link;
        }
        
        if (*pre != NULL && (*pre)->rchild == NULL) //若前驱结点的右子树为空,则建立后继线索
        {
            (*pre)->RTag = Thread;
            (*pre)->rchild = *p;
        }
        
        *pre = *p;    //中序遍历结点,保持pre指向p的前驱
        (*pre)->RTag = Link;//默认前驱结点右孩子非空
        
        InThreading(&(*p)->rchild, pre); //右子树线索化
    }
}

/*
函数名称:InThreading_2
函数功能:中序遍历二叉树,并将其中序线索化(非递归算法)
输入变量:BiThrTree *p:指向二叉树当前结点指针的指针
          BiThrTree *pre:指向二叉树树当前结点的前驱结点指针的指针
输出变量:无
*/
void InThreading_2(BiThrTree *root, BiThrTree *pre) //中序遍历二叉树,并将其中序线索化(非递归算法)
{
    BiThrTree stack[MAXSIZE];
    BiThrTree p = *root;
    int top = -1;
   
    while (p != NULL || top >= 0)
    {
        if (p != NULL) //先处理左子树
        {
            stack[++top] = p;
            p = p->lchild;
        }
        else
        {  
            p = stack[top--];
        //线索化当前结点及其前驱结点
            if (*pre != NULL && (*pre)->rchild == NULL)
            {
                (*pre)->RTag = Thread;
                (*pre)->rchild = p;
            }
            
            if (p->lchild == NULL)
            {
                p->LTag = Thread;
                p->lchild = *pre;
            }
            else
            {
                p->LTag = Link;
            }
            
            *pre = p;
            p = p->rchild; //线索化其右子树
        }
    }
}
    接下来我们讨论遍历中序线索树的算法。要想遍历中序线索树,必须先根据其特征,设计一个能返回结点前驱或后继的函数。
/*
函数名称:Successor
函数功能:返回结点p的后继
输入变量:BiThrTree p:指向中序线索树结点的指针
输出变量:BiThrTree: 指向结点后继的指针
若结点无右孩子,则由后继线索直接得到后继结点;否则后继为右子树的第一个结点(最左边结点)。
*/
BiThrTree Successor(BiThrTree p)
{
    if (p->RTag == Thread) //由后继线索直接得到
        return p->rchild;
   
    //后继为右子树的第一个结点(最左边结点)
    p = p->rchild;
    while (p->LTag == Link)
    {
        p = p->lchild;
    }
    return p;
}

/*
函数名称:Precursor
函数功能:返回结点p的前驱
输入变量:BiThrTree p:指向中序线索树结点的指针
输出变量:BiThrTree: 指向结点前驱的指针。
若结点无左孩子,则由前驱线索直接得到前驱结点;否则前驱为左子树的最后一个结点(最右边结点)。
*/
BiThrTree Precursor(BiThrTree p)
{
    if (p->LTag == Thread) //由前驱线索直接得到
        return p->lchild;
   
    //前驱为左子树的最后一个结点(最右边结点)
    p = p->lchild;
    while (p->RTag == Link)
    {
        p = p->rchild;
    }
    return p;
}

    顺序遍历中序线索树,需要先找到第一个结点,即最左边的结点,然后顺序访问其后继即可。代码如下:
/*
函数名称:InOrderTraverse_Thr
函数功能:顺序遍历中序线索树
输入变量:BiThrTree T:指向中序线索树头结点的指针
输出变量:无
*/
void InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p = T->lchild;
   
    while (p->LTag == Link) //先找到第一个结点(最左边结点)
    {
        p = p->lchild;
    }
    while (p != T)
    {
        printf("%c ", p->data);
        p = Successor(p);//返回结点p的后继
    }
}

因为线索树的头结点的右指针指向最后一个结点,所以逆序遍历中序线索树比顺序遍历要来的方便。代码如下:
/*
函数名称:ReInOrderTraverse_Thr
函数功能:逆序遍历中序线索树
输入变量:BiThrTree T:指向中序线索树头结点的指针
输出变量:无
*/
void ReInOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p = T->rchild; //p指向最后一个结点

    while (p != T)
    {
        printf("%c ", p->data);
        p = Precursor(p);//返回结点p的前驱
    }
}

《大话数据结构》中提供了一个顺序遍历中序线索树的函数,思路很清晰,代码页也很简洁,在这里和大家分享一下。
/*
函数名称:InOrderTraverse_Thr_1
函数功能:顺序遍历中序线索树
输入变量:BiThrTree T:指向中序线索树头结点的指针
输出变量:无
*/
void InOrderTraverse_Thr_1(BiThrTree T)
{
    BiThrTree p = T->lchild;
   
    while (p != T)
    {
        while (p->LTag == Link) //寻找第一个结点(最左边的结点)
        {
            p = p->lchild;
        }
        
        printf("%c ", p->data);
        
        while (p->RTag == Thread && p->rchild != T) //访问直接后续结点(直接由右指针指向)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        
        p = p->rchild; //访问右子树
    }
}

到这里,中序线索树的基本操作就介绍完了,大家可以尝试设计在中序线索树中插入新结点或删除结点的函数,其操作和循环双链表差不多,请试试看吧。

[ 本帖最后由 巧若拙 于 2014-10-2 09:45 编辑 ]
搜索更多相关主题的帖子: 信息 动态 二叉树 
2014-10-02 09:39
快速回复:线索二叉树基本操作详解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024193 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved