【二叉树】二叉树的深度优先遍历DFS(前中后序遍历)和

广度优先遍历BFS

二叉树的深度优先遍历有三种方式，分别是前序遍历、中序遍历和后序遍历。

前序遍历：先访问根节点，再访问左子树，最后访问右子树。

中序遍历：先访问左子树，再访问根节点，最后访问右子树。

后序遍历：先访问左子树，再访问右子树，最后访问根节点。

举个例子，对于以下二叉树：

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

它的前序遍历结果为：1 2 4 5 3 6 7

它的中序遍历结果为：4 2 5 1 6 3 7

它的后序遍历结果为：4 5 2 6 7 3 1

二叉树的广度优先遍历又称为层次遍历，它是从上到下、从左到右依次访问每个节点。具体实现可以使用队列来辅助实现。举个例子，对于以上的二叉树，其广度优先遍历结果为：1 2 3 4 5 6 7

相关问题

建立一棵二叉树，实现二叉树前序遍历、中序遍历、后序遍历遍历和其他操作。

好的，我来给你介绍一下二叉树和它的遍历方式。

二叉树是一种树形结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。

前序遍历是从根节点开始，先访问根节点，然后遍历左子树，最后遍历右子树。中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

下面我们来实现一个二叉树，并对它进行遍历。

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

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        node = TreeNode(val)
        if self.root is None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            while queue:
                curr = queue.pop(0)
                if curr.left is None:
                    curr.left = node
                    return
                elif curr.right is None:
                    curr.right = node
                    return
                else:
                    queue.append(curr.left)
                    queue.append(curr.right)

    def preorderTraversal(self):
        def dfs(node):
            if not node:
                return
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
        res = []
        dfs(self.root)
        return res

    def inorderTraversal(self):
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            res.append(node.val)
            dfs(node.right)
        res = []
        dfs(self.root)
        return res

    def postorderTraversal(self):
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)
        res = []
        dfs(self.root)
        return res

    def levelorderTraversal(self):
        queue = []
        res = []
        if self.root is None:
            return res
        queue.append(self.root)
        while queue:
            level = []
            for _ in range(len(queue)):
                curr = queue.pop(0)
                level.append(curr.val)
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            res.append(level)
        return res

在上面的代码中，我们定义了一个 `TreeNode` 类表示二叉树的每个节点，包括节点的值和左右子节点。然后我们定义了一个 `BinaryTree` 类，其中包括插入节点和遍历二叉树的方法。我们使用列表来实现队列，实现了二叉树的层序遍历。

接下来我们创建一个二叉树，并对它进行遍历：

tree = BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)

print("前序遍历：", tree.preorderTraversal())
print("中序遍历：", tree.inorderTraversal())
print("后序遍历：", tree.postorderTraversal())
print("层序遍历：", tree.levelorderTraversal())

输出结果如下：

前序遍历： [1, 2, 4, 5, 3]
中序遍历： [4, 2, 5, 1, 3]
后序遍历： [4, 5, 2, 3, 1]
层序遍历： [[1], [2, 3], [4, 5]]

这就是一个简单的二叉树的实现和遍历方式。

python已知二叉树的先序和中序遍历，输出二叉树的后序遍历

通过先序遍历可以得到二叉树的根节点，而中序遍历可以将左右子树分开。因此，可以通过这两个遍历序列构造出二叉树，然后再进行后序遍历。

以下是 Python 代码实现：

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

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    i = inorder.index(root_val)
    root.left = buildTree(preorder[1:i+1], inorder[:i])
    root.right = buildTree(preorder[i+1:], inorder[i+1:])
    return root

def postorderTraversal(root):
    res = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        res.append(node.val)
    dfs(root)
    return res

preorder = [1,2,4,5,3,6,7]
inorder = [4,2,5,1,6,3,7]
root = buildTree(preorder, inorder)
result = postorderTraversal(root)
print(result)

输出结果为：

[4, 5, 2, 6, 7, 3, 1]