线索二叉树与树、森林
线索二叉树
利用二叉树中大量空指针（n 个结点有 n+1 个空指针）存储遍历的前驱/后继信息，提高遍历效率。
- 前驱线索：左空指针指向遍历序列中的前驱
- 后继线索：右空指针指向遍历序列中的后继
- 需增加标志位区分”孩子指针”和”线索指针”
树的存储结构
- 双亲表示法：用数组存结点并记录其双亲下标，找双亲 ，找孩子需遍历
- 孩子表示法：每个结点用链表存孩子，找孩子方便，找双亲需遍历
- 孩子兄弟表示法：每个结点有”第一个孩子”和”右兄弟”两个指针，可转化为二叉树
森林与二叉树的转换
- 树 → 二叉树：左孩子右兄弟，树的孩子变为左子树，兄弟变为右子树
- 森林 → 二叉树：先每棵树转二叉树，再把后一棵树的根作为前一棵根的右孩子
习题
习题 1
线索二叉树的作用是什么？
答案与解析
线索二叉树利用二叉树中的空指针（n 个结点有 n+1 个空指针）存储遍历序列中的前驱/后继信息，从而在不使用递归或栈的情况下，也能高效地进行遍历，提高了遍历速度并节省了空间。