题31

题31

题目

( ) 的遍历仍需要栈的支持.
A. 前序线索树
B. 中序线索树
C. 后序线索树
D. 所有线索树

分析

后续线索树需要栈的帮助吧，这可能跟后续的非递归实现也有关系
就是后序遍历的时候每个结点好像进去了两遍？先深搜往里搜，最后回退出来（到根节点）再继续往右子树深搜
需要标记当前的搜索是什么时候进来的吧
哦哦哦，看了答案，这还是这个访问的逻辑顺序和树的物理结构上的顺序冲突的问题

解

C
后序线索树遍历时,最后访问根结点,若从右孩子 返回访问父结点,则由于结点 的右孩子不一定为空 (右指针无法指向其后继), 因此通过指针可能无法遍历整棵树。如下图所示, 结点中的数字表示遍历的顺序, 图(c)中结点 6 的右指针指向其右孩子 5 , 而不指向其后序后继结点 7, 因此后序遍历还需要栈的支持, 而图(a)和图(b)均可遍历。



(a) 先序线索树 (b) 中序线索树 (c) 后序线索树