二叉树的遍历和线索二叉树--先序二叉树和后续二叉树

张开发
• 2026/4/21 1:01:34 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

二叉树的遍历和线索二叉树--先序二叉树和后续二叉树
一、共同点1. 都是利用二叉链表n1个空指针改线索2. ltag、rtag 标记规则一样- ltag0左孩子ltag1前驱线索- rtag0右孩子rtag1后继线索3. 都可以不用栈、不用递归遍历4. 构造方式按对应遍历顺序遍历树用pre记录前驱1、先序线索二叉树先根遍历根 → 左 → 右1. 构造规则按照先序根→左→右遍历1. 先访问根2. 线索化左子树3. 线索化右子树4. 空左指针 → 前驱5. 空右指针 → 后继2. 先序线索树 遍历规律- 首结点根结点本身不用往左找- 找后继1. rtag1 → 直接右指针就是后继2. rtag0 → 先找左孩子没有再找右孩子3. 致命缺点先序线索二叉树无法找父结点容易死循环左子树线索会指回祖先遍历容易重复遍历4. 先序线索化代码逻辑pre null; void preThread(TNode root){ if(rootnull) return; //处理根 if(root.leftnull){ root.leftpre; root.ltag1; } if(pre!nullpre.rightnull){ pre.rightroot; pre.rtag1; } preroot; //先序根→左→右 if(root.ltag0) preThread(root.left); if(root.rtag0) preThread(root.right); }2、后序线索二叉树后根遍历左 → 右 → 根1. 构造规则按照后序左→右→根遍历整棵树1. 先线索化左子树2. 再线索化右子树3. 最后处理当前根结点4. 空指针改前驱、后继线索2. 后序线索树 遍历规律- 首结点最左下最深结点- 找前驱、后继非常麻烦- 必须知道双亲结点才能顺利找后继3. 最大难点后序线索二叉树查找前驱后继极复杂单纯靠线索走不完整必须额外记录父结点4. 后序线索化代码逻辑pre null; void postThread(TNode root){ if(rootnull) return; //后序左→右→根 postThread(root.left); postThread(root.right); //处理当前结点 if(root.leftnull){ root.leftpre; root.ltag1; } if(pre!nullpre.rightnull){ pre.rightroot; pre.rtag1; } preroot; }三种线索二叉树对比1.中序线索二叉树- 遍历最简单- 找前驱后继最简单- 不会死循环2. 先序线索二叉树- 构造简单- 找后继简单找前驱极难- 易死循环3. 后序线索二叉树- 构造麻烦- 找前驱后继都很难- 必须双亲指针辅助总结1. 只有中序线索二叉树遍历最方便、最常用2. 先序根最先访问首结点是根3. 后序根最后访问首尾都要深入子树找4. 先序、后序线索树不适合快速查找前后结点5. 三种线索树空间复杂度都是 O(1)不用栈

更多文章