线索二叉树与树、森林
利用二叉树中大量空指针(n 个结点有 n+1 个空指针)存储遍历的前驱/后继信息,提高遍历效率。
- 前驱线索:左空指针指向遍历序列中的前驱
- 后继线索:右空指针指向遍历序列中的后继
- 需增加标志位区分”孩子指针”和”线索指针”
- 双亲表示法:用数组存结点并记录其双亲下标,找双亲 ,找孩子需遍历
- 孩子表示法:每个结点用链表存孩子,找孩子方便,找双亲需遍历
- 孩子兄弟表示法:每个结点有”第一个孩子”和”右兄弟”两个指针,可转化为二叉树
- 树 → 二叉树:左孩子右兄弟,树的孩子变为左子树,兄弟变为右子树
- 森林 → 二叉树:先每棵树转二叉树,再把后一棵树的根作为前一棵根的右孩子
习题 1
线索二叉树的作用是什么?
解题思路:
本题考查线索二叉树的作用。思路是先指出二叉树中空指针的数量恰好与遍历序列中“前驱/后继”信息的条数相当,再说明把这些信息存入空指针后带来的两点好处。
详细步骤:
- 含 个结点的二叉树共有 个空指针,而遍历序列中需要记录的前驱、后继信息也正好是这些空指针能容纳的量。
- 线索二叉树就是把遍历序列中的前驱/后继信息填入相应的空指针,使结点在不改动结构的情况下携带线索。
- 由此带来的好处有二:一是不使用递归或栈也能高效地进行遍历,二是提高了遍历速度并节省了额外的栈空间。
最终答案:
线索二叉树利用二叉树中的空指针(n 个结点有 n+1 个空指针)存储遍历序列中的前驱/后继信息,从而在不使用递归或栈的情况下,也能高效地进行遍历,提高了遍历速度并节省了空间。
