企业官网建设流程全解析

1. 什么是线索二叉树

普通二叉树大量节点的left/right指针会为空，n 个节点的二叉树有 n+1 个空指针域，线索二叉树就是把这些空指针利用起来：

• 左空指针：指向中序遍历的前驱节点（左线索）
• 右空指针：指向中序遍历的后继节点（右线索） 同时新增两个标记位区分指针类型：
• leftTag：0 = 左孩子，1 = 左前驱线索
• rightTag：0 = 右孩子，1 = 右后继线索

2. 整体实现步骤

1. 定义线索二叉树节点类：数据、左右孩子、左右标记位
2. 先手动构建一棵测试二叉树（用你题目里的树：1、3、8、10、6、14）
3. 中序递归线索化：维护全局前驱节点pre
   • 递归线索化左子树
   • 当前节点左空：左指针指向pre，leftTag=1
   • 前驱节点右空：前驱右指针指向当前节点，pre.rightTag=1
   • 更新pre = 当前节点
   • 递归线索化右子树
4. 线索二叉树遍历（不用递归、栈，靠线索直接遍历）：
   • 先找中序第一个最左节点
   • 循环输出当前节点，再通过右孩子 / 右线索找后继

3. 关键难点说明

• 必须用中序遍历顺序做线索化（最常用）
• pre要作为成员变量，递归全程共享前驱状态
• 遍历优先判断rightTag：是线索直接跳后继；是孩子就找右子树最左节点

二、完整 Java 代码实现

java

运行

/** * 线索二叉树节点 */ class ThreadNode { int val; ThreadNode left; ThreadNode right; // 0：指向左右孩子；1：指向前驱/后继线索 int leftTag; int rightTag; public ThreadNode(int val) { this.val = val; } } /** * 中序线索二叉树实现 */ public class ThreadBinaryTree { // 线索化时记录上一个访问的前驱节点 private ThreadNode pre; public ThreadNode root; /** * 中序线索化主方法 */ public void inOrderThread() { pre = null; inOrderThreadRecursion(root); } /** * 递归完成中序线索化 * 流程：左子树线索化 → 处理当前节点线索 → 更新前驱 → 右子树线索化 */ private void inOrderThreadRecursion(ThreadNode node) { if (node == null) { return; } // 1.先线索化左子树 inOrderThreadRecursion(node.left); // 2.处理当前节点的左线索：左孩子为空，指向前驱pre if (node.left == null) { node.left = pre; node.leftTag = 1; } // 3.处理前驱节点的右线索：前驱右孩子为空，后继指向当前node if (pre != null && pre.right == null) { pre.right = node; pre.rightTag = 1; } // 更新前驱为当前节点，供下一轮使用 pre = node; // 4.线索化右子树 inOrderThreadRecursion(node.right); } /** * 线索二叉树中序遍历（无需栈/递归，利用线索遍历） */ public void threadInOrderList() { ThreadNode cur = root; while (cur != null) { // 第一步：找到中序第一个节点：一路向左找leftTag=0的最左节点 while (cur.leftTag == 0) { cur = cur.left; } // 输出当前节点 System.out.print(cur.val + " "); // 通过右线索不断找后继 while (cur.rightTag == 1) { cur = cur.right; System.out.print(cur.val + " "); } // rightTag=0说明是右孩子，切换到右子树继续循环 cur = cur.right; } } public static void main(String[] args) { // 构建题目中的二叉树结构 ThreadNode node1 = new ThreadNode(1); ThreadNode node3 = new ThreadNode(3); ThreadNode node8 = new ThreadNode(8); ThreadNode node10 = new ThreadNode(10); ThreadNode node6 = new ThreadNode(6); ThreadNode node14 = new ThreadNode(14); // 建立父子关系 node1.left = node3; node1.right = node6; node3.left = node8; node3.right = node10; node6.right = node14; ThreadBinaryTree tree = new ThreadBinaryTree(); tree.root = node1; // 执行中序线索化 tree.inOrderThread(); System.out.println("线索化后中序遍历结果："); // 理论结果：8 3 10 1 6 14 tree.threadInOrderList(); } }

三、代码逐模块解析

1. 节点类ThreadNode

• leftTag/rightTag：标记指针类型，是线索还是孩子
• 初始leftTag=rightTag=0，默认都是孩子指针

2. 递归线索化inOrderThreadRecursion

1. 递归左子树：先处理左边所有节点
2. 当前节点左为空：挂前驱线索，leftTag=1
3. 前驱节点右为空：把前驱的右指针挂当前节点做后继，rightTag=1
4. pre=node，把当前节点设为下一个节点的前驱
5. 递归右子树

3. 线索化遍历threadInOrderList

1. 外层循环遍历整棵树
2. 内层第一个while：找到中序起始节点（最左节点）
3. 输出节点后，若右指针是线索（rightTag=1），直接顺着线索取后继输出
4. 若右指针是孩子，跳到右子树重复找最左节点

四、运行结果

plaintext

线索化后中序遍历结果： 8 3 10 1 6 14

和你之前二叉树中序遍历结果完全一致，验证线索化正确。

五、拓展补充

1. 前序 / 后序线索化：只需要把递归遍历顺序改成前序（根→左→右）、后序（左→右→根），线索逻辑不变
2. 适用场景：需要频繁做二叉树中序遍历、查找前驱后继，线索化后遍历时间复杂度 O (n)，无栈空间开销
3. 缺点：节点增删时，要同步修改前后所有节点的线索，维护成本高