【数据结构】3——线索二叉树

数据结构3——线索二叉树

概念

• 传统的二叉树存储结构中，只能通过遍历的方式找到节点的前驱和后继。为了能快速找到节点在某种遍历序列中的前驱和后继，引入了线索的概念。

• 若节点的左子树为空，则将左指针指向其前驱节点；若节点的右子树为空，则将右指针指向其后继节点。这些指向前驱和后继的指针就称为线索。

• 线索二叉树的节点结构：
  通常包括数据域、左指针域、右指针域、左标志位和右标志位。
  标志位用于区分指针域指向的是子树还是线索。例如，左标志位为 0 表示左指针指向左子树，为 1 表示左指针是前驱线索；右标志位同理。

建立线索二叉树

对二叉树进行中序遍历。
在遍历过程中，记录当前节点的前驱节点。

对于当前节点：
如果左子树为空，则将左指针指向前驱节点，并设置左标志位为 1。
如果前驱节点的右子树为空，则将前驱节点的右指针指向当前节点，并设置前驱节点的右标志位为 1。

遍历线索二叉树

中序遍历线索二叉树：
从根节点开始，一直向左找到最左节点，作为遍历的起点。
然后依次访问当前节点，根据当前节点的右标志位判断右指针是否为后继线索，如果是则直接访问后继节点，否则通过常规方式找到右子树中的最左节点继续遍历。

例子

     1
   /   \
  2     3
 / \   / \
4   5 6   7

首先进行中序遍历并构建线索二叉树：
中序遍历序列为：4、2、5、1、6、3、7。

遍历过程中记录前驱节点，

• 对于节点 4，没有前驱，左子树为空，左指针为空，右指针指向节点 2，右标志位为 0（表示右指针指向右子树）。
• 对于节点 2，前驱为节点 4，左指针指向节点 4，左标志位为 1（表示左指针是线索），右指针指向节点 5，右标志位为 0。
• 对于节点 5，前驱为节点 2，左指针指向节点 2，左标志位为 1，右指针指向节点 1，右标志位为 0。
• 对于节点 1，前驱为节点 5，左指针指向节点 5，左标志位为 1，右指针指向节点 6，右标志位为 0。
• 对于节点 6，前驱为节点 1，左指针指向节点 1，左标志位为 1，右指针指向节点 3，右标志位为 0。
• 对于节点 3，前驱为节点 6，左指针指向节点 6，左标志位为 1，右指针指向节点 7，右标志位为 0。
• 对于节点 7，前驱为节点 3，左指针指向节点 3，左标志位为 1，没有后继，右指针为空。

遍历线索二叉树：

• 从最左节点 4 开始，访问节点 4。
• 由于节点 4 的右标志位为 0，通过右指针找到节点 2，访问节点 2。
• 节点 2 的右标志位为 0，找到节点 5，访问节点 5。
• 节点 5 的右标志位为 0，找到节点 1，访问节点 1。
• 节点 1 的右标志位为 0，找到节点 6，访问节点 6。
• 节点 6 的右标志位为 0，找到节点 3，访问节点 3。
• 节点 3 的右标志位为 0，找到节点 7，访问节点 7。