线索二叉树

二叉树有些节点没有左子树或没有右子树或左右子树都没有，那么就会存在空链接的情况，为了充分利用空链接，让其指向树的其他节点，这些指向其他节点的链接就是线索，这棵树也变成了线索二叉树。

二叉树变成线索二叉树的步骤

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 

优缺点

线索二叉树是对普通二叉树的一种优化，通过引入线索（线索化），可以提高对二叉树的遍历效率。：

优点：

1. 遍历效率提高： 线索二叉树在中序遍历时，不需要使用递归或栈，而是通过线索直接找到下一个节点，因此遍历效率较高。

2. 节省空间： 在线索二叉树中，引入的线索信息并不额外占用存储空间，因为线索是通过原有的左右子节点的空指针来表示的。相比于使用栈进行递归遍历，这节省了存储空间。

3. 简化代码逻辑： 由于线索化后的二叉树不需要递归或栈，可以简化中序遍历等算法的实现，减少代码的复杂性。

缺点：

1. 构建和维护的复杂性： 线索二叉树的构建和维护相对复杂，需要在插入、删除等操作时更新线索信息，容易引入错误。

2. 不适用于频繁修改的情况： 如果二叉树的结构经常变动，比如频繁地进行插入、删除操作，线索二叉树的维护可能会变得非常繁琐，效率可能不如普通二叉树。

3. 不利于其他遍历方式： 线索二叉树主要优化了中序遍历，对于其他遍历方式（如前序、后序）并没有明显的优势，甚至可能引入冗余的线索信息。

4. 占用额外的指针空间： 虽然线索信息不占用额外的存储空间，但对于每个节点都需要引入两个指针（左线索、右线索），可能导致额外的指针空间占用。

在选择是否使用线索二叉树时，需要根据具体应用场景来权衡其优缺点。如果主要是中序遍历的频繁操作，且对存储空间有一定要求，线索二叉树可能是一个合适的选择。然而，在频繁修改或其他遍历方式需要优化的情况下，可能需要考虑其他数据结构。