线索二叉树
二叉树有些节点没有左子树或没有右子树或左右子树都没有，那么就会存在空链接的情况，为了充分利用空链接，让其指向树的其他节点，这些指向其他节点的链接就是线索，这棵树也变成了线索二叉树。
二叉树变成线索二叉树的步骤
1. 二叉树先根据中序遍历的方式，进行排序（这样节点就直到其前驱节点、后继节点）
2. 判断每个节点是否存在空链接，然后把空链接线索化。
3. 线索标记： 如果该节点无左子节点，则线索/左子链接引用指向第1步排序后的该节点的前驱节点
4. 线索标记： 如果该节点无右子节点，则线索/右子链接引用指向第1步排序后的该节点的后继节点
示例：
1. 二叉树中序排序结果: HDIBEAFCG
2. 分别判断每个节点是否有空链接，有空链接的进行线索化处理
2.1 H节点：无左右子节点，存在空链接即需要线索化处理。因为H没有前驱节点，H的左子节点指向None（null）即空节点，H的右子节点指向D即指向H的后继节点
2.2 D节点：无空链接，无需线索化处理
2.2 I节点：无左右子节点，存在空链接即需要线索化处理。I的左子节点指向其前驱节点（D），I的右子节点指向其后继节点（B）
2.2 B节点：无空链接，无需线索化处理
2.3 E节点：无左右子节点，存在空链接即需要线索化处理。I的左子节点指向其前驱节点（B），I的右子节点指向其后继节点（A）
2.4 A节点：无空链接，无需线索化处理
2.5 F节点：无左右子节点，存在空链接即需要线索化处理。I的左子节点指向其前驱节点（A），I的右子节点指向其后继节点（C）
2.6 C节点：无空链接，无需线索化处理
2.7 G节点：无左右子节点，存在空链接即需要线索化处理。I的左子节点指向其前驱节点（C），I的右子节点指向其后继节点，因其无后继节点，因此为None（null）即空节点
python代码示例
# 线索树节点 class ThreadNode(object): def __init__(self, data='#'): self.data = data # 数据 self.lchild = None # 左子节点 self.rchild = None # 右子节点 self.ltag = 0 # 左线索，0表示有左子节点，1表示没有左子节点。该节点没有左子节点时，lchild指向该节点的前驱节点（前驱、后继节点是由其排序决定） self.rtag = 0 # 右线索，0表示有右子节点，1表示没有右子节点。该节点没有右子节点时rlchild指向该节点的后继节点（前驱、后继节点是由其排序决定） # 线索树 class BinaryThreadTree(object): def __init__(self, data_list): self.data_list = data_list # 创建树的头结点 self.headNode = ThreadNode() self.headNode.ltag = 0 # 有左子节点 self.headNode.rtag = 1 # 无右子节点 self.headNode.lchild = self.headNode # 为本身 self.preNode = ThreadNode() # 前驱节点 # 根据列表创建二叉树 def __createBinaryTree(self, root=None, pos=0): if pos >= len(self.data_list) or self.data_list[pos] == '#': # 递归结束条件 return None else: root = ThreadNode(self.data_list[pos]) # 递归建立左子树 root.lchild = self.__createBinaryTree(root, 2 * pos + 1) # 递归建立右子树 root.rchild = self.__createBinaryTree(root, 2 * pos + 2) return root # 访问当前节点的数据 def visitBinaryTreeNode(self, rootNode): if rootNode.data != '#': print(rootNode.data, end=' ') # 创建线索二叉树：首先创建二叉树，然后通过中序遍历线索化。这里使用了递归的方式。 def createInThread(self): rootNode = self.__createBinaryTree() if rootNode is None: self.headNode.lchild = self.headNode else: # lchild域的指针指向二叉树的根结点 self.headNode.lchild = rootNode self.preNode = self.headNode self.inThread(rootNode) # 处理最后一个结点 self.preNode.rtag = 1 self.preNode.rchild = self.headNode # rchild域的指针指向中序遍历时访问的最后一个结点 self.headNode.rchild = self.preNode # 中序遍历线索化:线索化过程中，如果节点没有左子节点，将左线索指向前驱节点；如果前驱节点没有右子节点，将右线索指向当前节点。 def inThread(self, treeNode): if treeNode is not None: # 递归, 线索化左子树 self.inThread(treeNode.lchild) if treeNode.lchild is None: # 当前结点没有左孩子 # 将当前结点的ltag置为1, 表示lchild域指向的是前驱 treeNode.ltag = 1 treeNode.lchild = self.preNode if self.preNode.rchild is None: # 前驱结点没有右孩子 # 将前驱结点的rtag置为1, 表示rchild域指向的是后继, 即当前的TreeNode self.preNode.rtag = 1 self.preNode.rchild = treeNode # 标记刚刚访问的结点为下个结点的前驱结点 self.preNode = treeNode self.inThread(treeNode.rchild) # 中序遍历线索二叉树 def inOrderThread(self): # treeNode就是树的根结点 treeNode = self.headNode.lchild while treeNode is not self.headNode: while treeNode.ltag == 0: # 找到了树最左边的那个结点(不一定是叶结点) treeNode = treeNode.lchild self.visitBinaryTreeNode(treeNode) while treeNode.rchild is not self.headNode and treeNode.rtag == 1: # 线索后继 treeNode = treeNode.rchild self.visitBinaryTreeNode(treeNode) # rtag=0就开始寻找右子树最左边那个结点 treeNode = treeNode.rchild if __name__ == '__main__': tree_obj = BinaryThreadTree('ABCDEFGHI#') tree_obj.createInThread() tree_obj.inOrderThread()
输出：
H D I B E A F C G
优缺点
线索二叉树是对普通二叉树的一种优化，通过引入线索（线索化），可以提高对二叉树的遍历效率。：
优点：
-
遍历效率提高： 线索二叉树在中序遍历时，不需要使用递归或栈，而是通过线索直接找到下一个节点，因此遍历效率较高。
-
节省空间： 在线索二叉树中，引入的线索信息并不额外占用存储空间，因为线索是通过原有的左右子节点的空指针来表示的。相比于使用栈进行递归遍历，这节省了存储空间。
-
简化代码逻辑： 由于线索化后的二叉树不需要递归或栈，可以简化中序遍历等算法的实现，减少代码的复杂性。
缺点：
-
构建和维护的复杂性： 线索二叉树的构建和维护相对复杂，需要在插入、删除等操作时更新线索信息，容易引入错误。
-
不适用于频繁修改的情况： 如果二叉树的结构经常变动，比如频繁地进行插入、删除操作，线索二叉树的维护可能会变得非常繁琐，效率可能不如普通二叉树。
-
不利于其他遍历方式： 线索二叉树主要优化了中序遍历，对于其他遍历方式（如前序、后序）并没有明显的优势，甚至可能引入冗余的线索信息。
-
占用额外的指针空间： 虽然线索信息不占用额外的存储空间，但对于每个节点都需要引入两个指针（左线索、右线索），可能导致额外的指针空间占用。
在选择是否使用线索二叉树时，需要根据具体应用场景来权衡其优缺点。如果主要是中序遍历的频繁操作，且对存储空间有一定要求，线索二叉树可能是一个合适的选择。然而，在频繁修改或其他遍历方式需要优化的情况下，可能需要考虑其他数据结构。