第3章 线索二叉树

文章目录

• 1. 线索二叉树

  • 1. 1 节 基本概念
  • 1. 2 节 线索二叉树的构建
  • 复制代码

    * 1\. 2\. 1 节 中序线索化的过程

  • 复制代码

    * 1\. 2\. 2 节 先续线索化的方法

  • 复制代码

    * 1\. 2\. 3 节 后续线索化的方式

• 1.3 线索二叉树及其遍历方法

  • 1.3.1 实现中序线索二叉树中的后续访问操作
  • 1.3.2 实现先序线索二叉树中的后续访问操作
  • 1.3.3 实现后序线索二叉树中的后续访问操作

重点

• 线索二叉树的构造。
• 线索二叉树的遍历。

1. 线索二叉树

1.1 基本概念

遍历二叉树是按照特定的规律将二叉树中的节点排列成一个线性序列。在该序列中，除了首尾两个节点外，每个节点都只有一个直接前驱和直接后继。

• 传统的二叉链表存储只能表示父子之间的单向关系，并不能直接获取到节点在遍历过程中的前驱与后续信息。
  • 在具有n个节点的二叉树结构中（每个节点平均拥有两个指针域），其中只有一个用于指向子节点而另一个则为空。

（1）定义
规定：

• 若无左子树，则将lchild指向其前驱节点。
  • 若无右子树，则让rchild指向其后继节点。
  • 引入两个标志ltag和r