二叉树的遍历和线索二叉树--中序线索二叉树的构造

一、为什么要用线索二叉树普通二叉链表- n 个结点一共2n 个指针域- 真正指向孩子的指针只有 n-1 个- 剩余 n1 个空指针空间浪费解决办法利用空左、空右指针存放中序遍历的前驱、后继结点加上标记位区分就是中序线索二叉树二、线索结点结构数据 data 左指针 lchild 左标记 ltag 右指针 rchild 右标记 rtag- ltag 0lchild 指向左孩子- ltag 1lchild 是前驱线索- rtag 0rchild 指向右孩子- rtag 1rchild 是后继线索三、构造核心规则中序左→根→右1. 按照中序遍历顺序递归遍历整棵树2. 定义全局指针 pre永远记录上一个访问过的结点3. 当前结点左孩子为空→ 左指针指向 preltag14. 前驱结点 pre 右孩子为空→ pre 右指针指向当前结点pre.rtag15. 遍历完当前结点更新 pre 当前结点四、一步步构造流程画图逻辑1. 初始化 pre null2. 递归线索化左子树3. 处理当前根结点绑定前驱线索4. 绑定前驱结点到当前结点的后继线索5. 更新前驱 pre6. 递归线索化右子树五、Java 标准构造代码1.线索结点类class InThreadNode { int data; InThreadNode left; InThreadNode right; int ltag; //0左孩子 1前驱线索 int rtag; //0右孩子 1后继线索 public InThreadNode(int data) { this.data data; left null; right null; ltag 0; rtag 0; } }2.中序线索化核心递归代码public class ThreadTree { static InThreadNode pre null; //记录前驱结点 //中序遍历实现二叉树线索化 public void createInThread(InThreadNode root) { if (root null) return; //1.递归线索化左子树 createInThread(root.left); //2.处理当前结点左空 → 指向前驱 if (root.left null) { root.left pre; root.ltag 1; } //3.处理前驱结点右空 → 指向当前结点后继 if (pre ! null pre.right null) { pre.right root; pre.rtag 1; } //前驱后移 pre root; //4.递归线索化右子树 createInThread(root.right); } }六、中序线索二叉树遍历不用栈、不用递归//线索树遍历 public void threadTraverse(InThreadNode root){ InThreadNode p root; //找到中序第一个结点最左下 while(p ! null p.ltag 0){ p p.left; } while(p ! null){ System.out.print(p.data ); //右是线索直接走后继 if(p.rtag 1){ p p.right; } //右是孩子找右子树最左下结点 else{ p p.right; while(p ! null p.ltag 0){ p p.left; } } } }七、考点1. 线索化本质 一次完整中序遍历2. pre 是连接前驱后继的关键3. 叶子结点左右指针全部是线索4. 线索二叉树无需递归、无需栈即可遍历5. n 个结点二叉链表固定空指针数量n1 个6. 中序线索树找前驱后继最简单先序、后序很复杂八、优缺点优点- 充分利用空闲指针不额外占用空间- 非递归快速遍历- 快速查询结点遍历前驱、后继缺点- 插入、删除结点麻烦需要重新修改所有线索- 树结构改动代价大