我要招人

去企业版

首页 > 试题广场 >

下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（

[单选题]

下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）

```
A
```
```
B
```
```
C
```
```
D
```

查看答案及解析

稳住！offer会来的

（1）先忽略虚线部分，只看实线，进行后序遍历，得dbca前驱后继关系

（2）考虑每个结点，当左孩子为空时，指向前驱；右孩子为空时指向后继。（用虚线）

结点d，无左右孩子，则指向前驱null，后继b

结点b, 无左孩子，则指向前驱d

结点c，无左右孩子，则指向前驱b，后继a

结点a,, 有左右孩子。

编辑于 2018-10-14 17:26:44 回复(2)

IM_Rocket

我觉得应该是这样：

编辑于 2017-04-06 09:07:00 回复(0)

朽木の半夏

补一点
B中序线索二叉树。
C前序线索二叉树。
D后续线索二叉树。

发表于 2017-09-27 23:10:20 回复(1)

求杨超越带好运😁

当以二叉链表作为存储结构时，只保存了左右孩子结点信息，而不能够得到结点在任一序列中的前驱和后继信息，为了解决以上问题，用如下结构存储：

lchild

LTag

data

RTag

rchild

其中：

LTag = 0 lchild域指示结点的左孩子

LTag =1 lchild域指示结点的前驱

RTag = 0 rchild域指示结点的左孩子

RTag =1 rchild域指示结点的后继

因为是后续线索树，先求此树的后续遍历为dbca,

a 有左右孩子，不考虑前驱后继

b 有右孩子无左孩子，LTag =1, 指向前驱结点d

c 左右孩子都没有，LTag =1, 指向前驱结点b, RTag =1,指向后继结点a

d 左右孩子都没有，LTag =1, 指向前驱结点,无前驱结点所以指向Null。 RTag =1,指向后继结点b

发表于 2018-12-17 17:47:16 回复(0)

LearningFromDoing

我的理解是：线索二叉树的某子女为空时，left/right域指向其前驱/后继，由于是后序线索树，且该树的后序遍历为dbca，因此对应节点的子女域在填写前驱和后继时遵循该顺序，例如结点d，没有子女，而d没有前驱，因此left域为null，而d的后继为b，因此right域指向b，以此类推即可。

编辑于 2016-12-23 19:55:18 回复(0)

xxxxxxxxxxxxxxxa

dbca

左指针指向前驱，右指针指向后继，当然前提左右指针原本为空。

发表于 2018-06-23 22:20:11 回复(0)

侯卿

只有中序是两个空域，排除B。后序的空域就是开始，在左子树(有的话)，排除C。此时只用看有空域的后继是否符合后序，选D。

发表于 2018-03-31 16:58:32 回复(0)

滴滴打🐷

首先是不看实线只看虚线，后序遍历为dcba 然后对于节点d 没有左右节点因此，做边指向null右边指向c 依次类推

发表于 2021-06-24 17:08:24 回复(0)

任我游

按照遍历顺序，左支为空，指向前驱，右支为空，指向后继。

发表于 2017-08-14 10:24:03 回复(0)

philian

就是后序遍历，根据遍历次序确定一个线性表

发表于 2016-12-17 09:10:21 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

10条回答 544收藏 14879浏览

下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（

问题信息

热门推荐

相关试题