已知线索二叉树in-order线索遍历方法，如何实现其pre-order与post-order遍历？

阿华AIGC实验室

2026-5-21

嘿，这个问题问得好！既然你已经摸透了中序线索二叉树的遍历逻辑，那咱们来一步步拆解前序（Pre-order）和后序（Post-order）的实现思路——核心都是利用线索指针来规避递归或者栈的开销，但因为遍历顺序不同，处理逻辑会有明显区别。

前序遍历（Pre-order Traversal: 根→左→右）

前序的核心是先访问当前节点，再处理左子树，最后处理右子树。针对中序线索二叉树（也就是你提到的threaded BST，线索指向中序的前驱/后继），我们可以用以下循环逻辑实现无栈遍历：

# 伪代码示例，假设节点有left、right指针，且用is_thread_left/is_thread_right标记是否为线索
current = root
while current is not None:
    # 前序优先访问当前节点
    print(current.value)
    
    # 如果有真实左孩子（不是线索），直接往左走
    if not current.is_thread_left:
        current = current.left
    else:
        # 没有左孩子，找下一个前序节点
        # 沿着右指针走，如果是线索就一直跳，直到找到有真实右孩子的节点
        while current.is_thread_right and current.right is not None:
            current = current.right
        # 走到这里，current的right要么是真实右孩子，要么是null
        current = current.right

逻辑解释

从根节点开始，第一时间访问它——这是前序的核心要求。
只要有真实左孩子，就优先往左走，因为前序要先处理左子树。
当左指针是线索（说明左子树为空），就看右指针：如果右指针是线索，说明这个节点的中序后继，但前序里我们需要跳过这些线索节点，直到找到一个有真实右孩子的节点，然后转向它的右子树；如果右指针本身就是真实孩子，直接过去即可。

举个简单例子：假设树是1(null,2(3,null))，中序线索后，3的右指针是线索指向2，2的右是线索指向1的后继（假设为null）。前序遍历顺序是1→2→3，用上面的逻辑：

访问1，左是线索，所以看右，2是真实孩子，移动到2。
访问2，左是真实孩子3，移动到3。
访问3，左是线索，右是线索指向2，所以沿着线索走到2，然后2的右是线索指向null，current变成null，遍历结束。完美符合前序顺序。

后序遍历（Post-order Traversal: 左→右→根）

后序就麻烦一些了，因为它要求最后访问根节点，而中序线索只提供了中序的前驱/后继，没法直接帮我们回溯父节点。这里分两种场景讨论：

场景1：节点带有父指针

如果你的线索树节点额外存储了父指针，那实现起来会顺畅很多：

current = root
prev = None
while current is not None:
    # 先尝试往左走，只要左孩子是真实节点且没被访问过
    if not current.is_thread_left and prev != current.left and prev != current.right:
        current = current.left
    # 左子树处理完了，尝试往右走
    elif not current.is_thread_right and prev != current.right:
        current = current.right
    # 左右都处理完了，访问当前节点
    else:
        print(current.value)
        prev = current
        # 回溯父节点
        if current == root:
            break  # 遍历结束
        parent = current.parent
        # 如果当前是父节点的左孩子，接下来要处理父节点的右子树
        if parent.left == current:
            current = parent
        # 如果当前是父节点的右孩子，继续回溯到祖父节点
        else:
            current = parent

逻辑解释

我们用prev变量记录上一个访问的节点，确保只有当左、右子树都被处理完（prev是左或右孩子），才会访问当前节点。访问完成后，根据当前节点是父节点的左/右孩子，决定下一步是处理父节点的右子树，还是继续回溯。

场景2：节点没有父指针（纯线索树）

这种情况我们没法直接回溯，只能用临时修改线索的方法（类似Morris遍历思路），遍历完成后再恢复线索，避免破坏树结构：

# 伪代码，创建虚拟节点辅助遍历
dummy = Node()
dummy.left = root
current = dummy

while current is not None:
    if current.left is None or current.is_thread_left:
        current = current.right
    else:
        # 找到左子树的中序最右节点（这个节点的右指针是线索，指向current）
        predecessor = current.left
        while not predecessor.is_thread_right and predecessor.right != current:
            predecessor = predecessor.right
        
        if predecessor.right != current:
            # 临时修改线索，让predecessor的右指针指向current，标记已访问
            predecessor.right = current
            predecessor.is_thread_right = True  # 临时改成线索
            current = current.left
        else:
            # 恢复线索，反向遍历左子树的右边界并访问
            predecessor.is_thread_right = False
            predecessor.right = None  # 恢复原线索（假设原线索是null）
            
            # 反向遍历左子树的右边界，这部分是后序要最后访问的
            temp = current.left
            reverse_path = []
            while temp != current:
                reverse_path.append(temp)
                temp = temp.right if not temp.is_thread_right else temp.right
            # 反向输出路径
            for node in reversed(reverse_path):
                print(node.value)
            
            current = current.right