二叉树的遍历和线索二叉树--线索二叉树

张开发
2026/4/20 9:11:02 15 分钟阅读

分享文章

二叉树的遍历和线索二叉树--线索二叉树
一、引出线索二叉树的原因1. 普通二叉链表n 个结点总共有 2n 个指针域2. 有效孩子指针只用了 n-1 个3. 剩余n1 个指针是空指针极度浪费空间思路把空指针利用起来- 左空指针 → 指向该结点---遍历前驱- 右空指针 → 指向该结点---遍历后继这种用指针记录遍历先后关系的二叉树 线索二叉树二、线索二叉树结点结构比普通二叉结点多两个标记位- data数据- lchild左孩子 / 前驱线索- rchild右孩子 / 后继线索- ltag左标记- ltag 0lchild 指向左孩子- ltag 1lchild 是前驱线索- rtag右标记- rtag 0rchild 指向右孩子- rtag 1rchild 是后继线索三、三种线索二叉树按照遍历方式划分1.先序线索二叉树2. 中序线索二叉树3. 后序线索二叉树四、核心特点1. 充分利用空闲空指针不额外占用内存2.不用递归、不用栈就可以遍历整棵树3. 可以快速查找结点在遍历序列中的前驱、后继4. 遍历速度更快空间复杂度更低5. 本质二叉树 静态链表五、中序线索二叉树规律1. 最左结点左线索为空无前驱2. 最右结点右线索为空无后继3. 叶子结点左右全是线索4. 二叉树 头尾结点连成循环双向线索链表找前驱后继- 叶子结点直接顺着线索找- 非叶子结点依然要靠左右子树查找六、优缺点优点1. 非递归遍历二叉树无需栈2. 快速查询前驱、后继结点3. 空间利用率高缺点1. 插入、删除结点麻烦需要重新修改线索2. 先序、后序线索树查找前驱后继复杂3. 不如递归遍历代码直观

更多文章