【数据结构】线索化二叉树中序线索化的递归写法和非递归写法

线索化二叉树是一种特殊的二叉树，它的每个节点都有一个指向前驱节点和后继节点的指针，这些指针称为线索。线索化二叉树可以提高遍历二叉树的效率。

中序线索化二叉树的递归写法如下：

def in_order_threading(root):
    global pre
    pre = None
    def in_order_threading_recursive(node):
        global pre
        if not node:
            return
        in_order_threading_recursive(node.left)
        if not node.left:
            node.left = pre
            node.ltag = 1
        if pre and not pre.right:
            pre.right = node
            pre.rtag = 1
        pre = node
        in_order_threading_recursive(node.right)
    in_order_threading_recursive(root)

其中，`node.ltag` 和 `node.rtag` 分别表示节点的左指针和右指针是否是线索，如果是线索，则为1，否则为0。

中序线索化二叉树的非递归写法可以使用栈来实现。具体步骤如下：

1. 从根节点开始，找到最左边的叶子节点，并将路径上所有节点入栈。
2. 当栈不为空时，弹出栈顶节点，并将其线索化。
3. 如果当前节点有右儿子，则将右儿子及其左子树中所有节点入栈，否则继续弹出栈顶节点。

代码实现如下：

def in_order_threading(root):
    pre = None
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if not node.left:
            node.left = pre
            node.ltag = 1
        if pre and not pre.right:
            pre.right = node
            pre.rtag = 1
        pre = node
        node = node.right if not node.rtag else None

需要注意的是，在非递归写法中，需要判断当前节点的右指针是否是线索，如果是线索，则直接将下一个节点设置为该线索指向的节点。