二叉树-扩展

线索二叉树

  1. n个节点的二叉链表,每个节点有指向左右孩子的两个指针域,所以一共有2n个指针域,n-1条分支线数。存在2n-(n-1)即n+1个空指针域,这些空间不做任何事情,白白浪费内存资源。
  2. 只有遍历一次之后才知道某个节点的前驱和后继,每次都需要遍历的话这是很大的时间浪费。

综合以上两个角度,我们可以利用这些空地址来存放指向节点在某种遍历次序下的前驱和后继节点的地址。我们把这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树。

线索二叉树就是把一颗二叉树转变成一个双向链表,这样对我们的插入、删除、查找节点带来方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。

线索二叉树结构

二叉树线索存储结构定义如下:

typedef enum {Link, Thread} PointerTag;// 0:表示左、右孩子指针,1:表示前驱或后继的线索

typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;/* 左右孩子指针 */
    PointerTag LTag;/* 左标志 */
    PointerTag RTag;/* 右标志 */
} BiThrNode, *BiThrTree;

线索化的过程就是在遍历的过程中修改空指针的过程。代码如下所示:

BiThrTree pre;/* 全局变量,始终指向刚刚访问过的节点 */

void InThreading(BiThrTree p)
{
    if  (p)
    {
        InThreading(p->lchild);// 线索化左子树
        if  (!p->lchild)/* 当前节点没有左孩子 */
        {
            p->LTag = Thread;/* 前驱线索 */
            p->lchild = pre;/* 左孩子指针域指向前驱 */
        }
        if (!pre->rchild)/* 前驱没有右孩子 */
        {
            pre->RTag = Thread;/* 后继线索 */
            pre->rchild = p;/* 前驱右孩子指针域指向当前节点p */
        }
        pre = p;/* 访问过的节点开始移动 */
        InThreading(p->rchild);// 线索化右子树
    }
}

遍历线索二叉树等于是操作一个双向链表结构,给它添加一个头节点,这样我们既可以从第一个节点起顺后继遍历,也可以从最后一个节点起顺前驱遍历。代码如下:

Status InOrderTraverse_Thr(BiThrTree T)
{
    BiThrTree p;
    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;
    }
    return OK;
}

这样既充分利用了空指针域的空间,又保证创建时一次遍历就可以一直使用前驱、后继的信息。如果所用二叉树需要经常遍历或查找节点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构是非常不错的选择。

树、森林与二叉树的转换

TODO:

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,480评论 0赞 12
  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,916评论 1赞 31
  • 四、树与二叉树 1. 二叉树的顺序存储结构 二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有...
    MinoyJet阅读 1,841评论 0赞 7
  • 原链接:理解线索二叉树|CloudWong 线索二叉树原理 遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一...
    简Cloud阅读 8,641评论 1赞 16
  • 一、 概念 二叉树按照先序、中序、后续遍历的方法形成一个线性序列后,每个结点(除第一个和最后一个外),都有且仅有一...
    Qi0907阅读 1,784评论 0赞 1

友情链接更多精彩内容