数据结构——Threaded Binary Tree (TBT)

文章结构概览

• 一、线索二叉树（TBT）的概念解析
  • 二、构建线索二叉树的方法
  • 三、线索二叉树的具体实现方式

---

一、什么是线索二叉树（TBT）？

线索二叉树作为一种改进型的二叉树结构，对采用结构体指针方式实现的二叉树进行了顺序遍历效率的提升。

通常情况下，利用结构体指针来构建二叉树的方法如图所示：

在构建二叉树过程中，若采用结构体指针的方式，由于二叉树并非完全满，将产生大量无实际意义的指针。即便二叉树为满二叉树，其叶子节点的左右子指针依然为空。面对大规模数据处理的需求，这种指针资源的浪费存在较大风险，但这一问题在结构体指针方案中是难以规避的，因此我们使用结构体指针的方式也难以避免该问题。

当对二叉树进行非从根节点开始的顺序遍历时，若要确定某节点的前驱与后继节点，则必须重新从根节点出发进行一次遍历。

为了避免重复遍历的问题，我们可采取以下两种解决方法：

1. 建立一个新的数组，在首次遍历过程中记录相关信息。
2. 本文所介绍的线索二叉树方案。与上述方法相比，该方案无需额外建立数组，而是直接利用二