遍历二叉树和线索二叉树

遍历二叉树是指按照某种顺序依次访问二叉树中的所有节点。常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。其中前序遍历的访问顺序是先访问根节点，再访问左子树，最后访问右子树；中序遍历的访问顺序是先访问左子树，再访问根节点，最后访问右子树；后序遍历的访问顺序是先访问左子树，再访问右子树，最后访问根节点。

线索二叉树是在普通二叉树的基础上增加了指向前驱和后继节点的线索，使得在遍历二叉树时可以不需要使用递归或者栈等数据结构，从而节省空间和提高效率。线索二叉树分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种类型。其中，前序线索二叉树将左右子树都指向后继节点，中序线索二叉树将左子树指向前驱节点，右子树指向后继节点，后序线索二叉树将左子树和右子树都指向前驱节点。

相关问题

遍历二叉树和线索二叉树的方法

遍历二叉树的方法有三种：先序遍历、中序遍历和后序遍历。其中，先序遍历是指先遍历根节点，再遍历左子树和右子树；中序遍历是指先遍历左子树，再遍历根节点和右子树；后序遍历是指先遍历左子树和右子树，再遍历根节点。

线索二叉树是在二叉树的基础上，通过添加线索（即前驱和后继指针）来实现遍历的优化。线索二叉树的遍历方法有两种：中序遍历和后序遍历。其中，中序遍历是指按照节点的中序遍历顺序遍历线索二叉树；后序遍历是指按照节点的后序遍历顺序遍历线索二叉树。

举例说明：

//先序遍历二叉树
public void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

//中序遍历二叉树
public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

//后序遍历二叉树
public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

//中序遍历线索二叉树
public void inOrderThreaded(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        while (cur.left != null && !cur.left.isThreaded) {
            cur = cur.left;
        }
        System.out.print(cur.val + " ");
        if (cur.right != null && cur.isThreaded) {
            cur = cur.right;
        } else {
            cur = cur.right;
            while (cur != null && !cur.isThreaded) {
                cur = cur.left;
            }
        }
    }
}

//后序遍历线索二叉树
public void postOrderThreaded(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        while (cur.left != null && !cur.left.isThreaded) {
            cur = cur.left;
        }
        while (cur.right != null && cur.isThreaded) {
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
}

采用前序序列构建二叉树并且前序遍历二叉树，中序遍历二叉树，后序遍历二叉树和层次遍历二叉树的代码

在Python中，我们可以使用递归或栈来构建二叉树并进行各种遍历。这里是一个使用前序（pre-order）、中序（in-order）和后序（post-order）遍历构建二叉树的例子：

首先，我们需要创建一个二叉树节点的结构：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

接下来，我们可以通过前序遍历构建二叉树：

def build_tree(preorder):
    if not preorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    index = inorder.index(root_val)  # 假设inorder已知
    root.left = build_tree(preorder[1:index])
    root.right = build_tree(preorder[index+1:])
    return root

# 假设inorder列表已知
inorder = ...  # 中序遍历的结果
tree = build_tree(preorder)

中序遍历二叉树，如果我们已经有了前序遍历和后序遍历，可以通过两者的组合找到每个节点的位置，如下所示：

def in_order_traversal(root):
    if root is not None:
        in_order_traversal(root.left)
        print(root.val, end=" ")
        in_order_traversal(root.right)

in_order_traversal(tree)

后序遍历也可以类似处理：

def post_order_traversal(root):
    if root is not None:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val, end=" ")

post_order_traversal(tree)

至于层次遍历（广度优先搜索），通常使用队列：

from collections import deque

def level_order_traversal(root):
    if root is None:
        return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        current_level = [queue.popleft().val for _ in range(level_size)]
        result.append(current_level)
        if root.left:
            queue.append(root.left)
        if root.right:
            queue.append(root.right)
    return result

level_orders = level_order_traversal(tree)

注意：在这个例子中，我们需要预先知道中序遍历的结果，因为它是构造二叉树的关键。如果你只有前序和后序遍历，你需要另外一种方法来解决，比如利用线索二叉树。