数据结构——线索二叉树

简介: 数据结构——线索二叉树

线索二叉树原理


对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为
线索,加上线索的二叉树称为
线索二叉树

这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树中序线索二叉树后序线索二叉树三种。
注意:线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。

本质

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继)。对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到。为了容易找到前驱和后继,有两种方法。一是在结点结构中增加向前和向后的指针,这种方法增加了存储开销,不可取;二是利用二叉树的空链指针

分析

通过二叉树的中序遍历得:

  D B E A F C
  D的前驱是空后继是B
  B的前驱是D后继是E
  E的前驱是B后继是A
  F的前驱是A后继是C
  C的前驱是F后继是空

如下图:
在这里插入图片描述
为了区分lchild是指向左孩子还是指向它的前继,rchild是指向右孩子还是指向它的后继
我们再在每个结点再增加两个标志域ltag和rtag,里面存放0和1在这里插入图片描述
其中:

  1. ltag为0时指向该节点的左孩子,为1时指向该节点的前驱
  2. rtag为0时指向该节点的右孩子,为1时指向该节点的后继

线索二叉数结构的实现

线索二叉数存储结构定义

typedef char TElemType;
typedef enum {
    Link,Thread}PointerTag;
typedef struct BiThrNode
{
    
    TElemType data;
    struct BiThrNode* lchild;
    struct BiThrNode* rchild;
    PointerTag ltag;
    PointerTag rtag;
}BiThrNode;

二叉树线索化

线索化的过程就是在遍历的过程修改空指针的过程

BiThrNode* pre = NULL;  //全局变量,始终指向刚刚访问过的结点
void InThreading(BiThrNode* p)
{
    
    if (p)
    {
    
        InThreading(p->lchild);    //递归左数进行线索化
        if (!p->lchild)          //前驱线索
        {
    
            p->ltag = Thread;
            p->lchild = pre;
        }
        if (!pre->rchild)    //后继线索
        {
    
            pre->rtag = Thread;
            pre->rchild = p;
        }
        pre = p;
        InThreading(p->rchild);  //递归有树线索化
    }
}

分析:
if (!p->lchild) 表示如果某节点的左指针域为空,则将其前驱赋连上刚刚访问过的结点pre,
即p->lchild = pre,并将标记进行修改p->ltag = Thread;
if (!pre->rchild) 表示如果刚刚访问过的结点pre的右指针域为空,则将它的后继连上正在访问的结点,
即pre->rchild = p,并将标记进行修改pre->rtag = Thread

线索二叉树的遍历

void InOrderTraverse(BiThrNode* T)
{
    
    while (T)
    {
    
        while (T->ltag == Link)
        {
    
            T = T->lchild;
        }
        printf("%c ", T->data);
        while (T->rtag == Thread && T->rchild != NULL)
        {
    
            T = T->rchild;
            printf("%c ", T->data);
        }
        T = T->rchild;
    }
}

分析:
while (T->ltag == Link)从根节点开始遍历,如果左标记是Link让它一直循环下去,
直到找到标记为Thread的的结点,也就是要遍历的第一个结点,然后根据后驱指针找到后继结点
后面就是重复以上过程,直到遍历完整个二叉数。

总结

如果所用的二叉数需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉数是一个很好的选择;

相关文章
|
28天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
94 8
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
25 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
28 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
28 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
26 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)
|
2月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
2月前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解