线索二叉树核心思路讲解

1. 什么是线索二叉树普通二叉树大量节点的left/right指针会为空n 个节点的二叉树有 n1 个空指针域线索二叉树就是把这些空指针利用起来左空指针指向中序遍历的前驱节点左线索右空指针指向中序遍历的后继节点右线索 同时新增两个标记位区分指针类型leftTag0 左孩子1 左前驱线索rightTag0 右孩子1 右后继线索2. 整体实现步骤定义线索二叉树节点类数据、左右孩子、左右标记位先手动构建一棵测试二叉树用你题目里的树1、3、8、10、6、14中序递归线索化维护全局前驱节点pre递归线索化左子树当前节点左空左指针指向preleftTag1前驱节点右空前驱右指针指向当前节点pre.rightTag1更新pre 当前节点递归线索化右子树线索二叉树遍历不用递归、栈靠线索直接遍历先找中序第一个最左节点循环输出当前节点再通过右孩子 / 右线索找后继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) { // 第一步找到中序第一个节点一路向左找leftTag0的最左节点 while (cur.leftTag 0) { cur cur.left; } // 输出当前节点 System.out.print(cur.val ); // 通过右线索不断找后继 while (cur.rightTag 1) { cur cur.right; System.out.print(cur.val ); } // rightTag0说明是右孩子切换到右子树继续循环 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. 节点类ThreadNodeleftTag/rightTag标记指针类型是线索还是孩子初始leftTagrightTag0默认都是孩子指针2. 递归线索化inOrderThreadRecursion递归左子树先处理左边所有节点当前节点左为空挂前驱线索leftTag1前驱节点右为空把前驱的右指针挂当前节点做后继rightTag1prenode把当前节点设为下一个节点的前驱递归右子树3. 线索化遍历threadInOrderList外层循环遍历整棵树内层第一个while找到中序起始节点最左节点输出节点后若右指针是线索rightTag1直接顺着线索取后继输出若右指针是孩子跳到右子树重复找最左节点四、运行结果plaintext线索化后中序遍历结果 8 3 10 1 6 14和你之前二叉树中序遍历结果完全一致验证线索化正确。五、拓展补充前序 / 后序线索化只需要把递归遍历顺序改成前序根→左→右、后序左→右→根线索逻辑不变适用场景需要频繁做二叉树中序遍历、查找前驱后继线索化后遍历时间复杂度 O (n)无栈空间开销缺点节点增删时要同步修改前后所有节点的线索维护成本高