线索二叉树与无栈遍历

考点定位

本课深化 线索二叉树与无栈遍历。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

线索化利用空指针保存遍历前驱和后继，并用tag区分孩子指针与线索。不同遍历次序产生不同线索关系。

算法推演

中序线索树找后继：若rtag为线索，直接取右指针；否则进入右子树后沿真实左孩子走到最左结点。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

任何指针访问前先检查tag；线索绝不能当作真实孩子继续递归。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：n结点二叉链表有2n个指针域和n-1条孩子边，因此空指针为n+1。

随课应用

含8个结点的普通二叉链表共有多少个空指针域，可供线索化利用？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。