实验题4:实现二叉树的中序线索化

二叉树的中序线索化是将二叉树中的每个节点都指向其中序遍历的前驱和后继节点。这个过程需要对二叉树进行中序遍历，并将每个节点的左右指针修改为指向其前驱和后继节点。下面是中序线索化的实现代码：

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.left_thread = None
        self.right_thread = None

def inorder_threading(root):
    if root is None:
        return
    stack = []
    cur = root
    pre = None
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if cur.left is None:
            cur.left = pre
            cur.left_thread = True
        if pre and pre.right is None:
            pre.right = cur
            pre.right_thread = True
        pre = cur
        cur = cur.right if not cur.right_thread else None

if __name__ == '__main__':
    root = Node(1, Node(2), Node(3))
    inorder_threading(root)
    print(root.left.val)  # 2
    print(root.left.right)  # 1
    print(root.left.right_thread)  # True
    print(root.right.left)  # 1
    print(root.right.left_thread)  # True
    print(root.right.val)  # 3

上面的代码中，我们定义了一个 `Node` 类表示二叉树的节点。`left_thread` 和 `right_thread` 分别表示当前节点的左右指针是否是线索。初始时，二叉树的所有节点的 `left_thread` 和 `right_thread` 都是 `None`。

`inorder_threading` 函数实现了中序线索化的过程。我们使用一个栈来辅助进行中序遍历。对于每个节点，如果其左子节点为空，则将其左指针指向其中序遍历的前驱节点，并将 `left_thread` 标记为 `True`。如果其前驱节点的右指针为空，则将其右指针指向当前节点，并将 `right_thread` 标记为 `True`。

最后，我们可以验证中序线索化的结果是否正确。在上面的代码中，我们打印了一些节点的值和线索情况。可以看到，对于一个节点，其左指针指向的是其中序遍历的前驱节点，而右指针则指向其中序遍历的后继节点。