线索二叉树的基本概念和构造
标签: 数据结构
学习人数: 7417


全屏播放
赞赏支持

产生背景

现有一棵结点数目为n的二叉树,采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域,而结点为n的二叉树一共有n-1条有效分支路径。那么,则二叉链表中存在2n-(n-1)=n+1个空指针域。那么,这些空指针造成了空间浪费。
例如:下图所示一棵二叉树一共有10个结点,空指针^有11个。

此外,当对二叉树进行中序遍历时可以得到二叉树的中序序列。例如:上图所示二叉树的中序遍历结果为HDIBJEAFCG,可以得知A的前驱结点为E,后继结点为F。但是,这种关系的获得是建立在完成遍历后得到的,那么可不可以在建立二叉树时就记录下前驱后继的关系呢,那么在后续寻找前驱结点和后继结点时将大大提升效率。

 

线索化

现将某结点的空指针域指向该结点的前驱后继,定义规则如下:

若结点的左子树为空,则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空,则该结点的右孩子指针指向其后继结点。

这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种次序遍历,并添加线索的过程称为线索化。

图中黑色点画线为指向后继...

登录查看完整内容


课后作业

课后习题

 

【2014年真题】若对如下的二叉树进行中序线索化,则结点 x 的左、右线索指向的结点分别是 ()

A.e、c         B.e、a         C.d、c         D.b、a 

参考答案:D
答案解析:线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点, 所以先写出二叉树的中序遍历序列:edbxac,中序遍历中在 x 左边和右边的字符,就是它在 中序线索化的左、右线索,即 b、a,选 D。 

 

【2013年真题】若X是后序线索二叉树中的叶结点,且X存在左兄弟结点Y,则X的右线索指向的是()
A. X 的父结点                 B. 以 Y 为根的子树的最左下结点 
C. X 的左兄弟结点 Y         D. 以 Y 为根的子树的最右下结点 

参考答案:A
答案解析:根据后续线索二叉树的定义,X 结点为叶子结点且有左兄弟,那么这个结点为右孩子结点,利用后续遍历的方式可知 X 结点的后继是其父结点,即其右线索指向的是父结点。 

 

【2010年真题】下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是()

参考答案:D
答案解析:考查线索二叉树的基本概念和构造。
题中所给二叉树的后序序列为 dbca 。结点 d 无前驱和左子树,左链域空,无右子树,右链域指向其后继结点 b;结点 b 无左子树,左链域指向其前驱结点 d;结点 c 无左子树,左链域指向其前驱结点 b,无右子树,右链域指向其后继结点 a。 


登录后发布评论

暂无评论,来抢沙发