Jzoj3901 二叉查找树的构建与遍历

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的左子树上的所有元素都小于该节点，而右子树上的所有元素都大于该节点。这种特性使得二叉查找树在搜索、插入和删除操作上具有高效性能。

构建二叉查找树

要构建一个二叉查找树，我们需要遵循以下步骤：

1. 根节点的确定：选择一个关键值作为根节点。
2. 左子树的构建：对于根节点的每个左子节点，递归地选择一个关键值小于根节点的节点作为子节点。
3. 右子树的构建：对于根节点的每个右子节点，递归地选择一个关键值大于根节点的节点作为子节点。

下面是一个简单的Python代码示例，用于构建一个二叉查找树：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def insert(root, val):
    if root is None:
        return TreeNode(val)
    else:
        if val < root.val:
            root.left = insert(root.left, val)
        else:
            root.right = insert(root.right, val)
    return root
def build_bst(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    for i in range(1, len(arr)):
        root = insert(root, arr[i])
    return root

这个代码定义了一个TreeNode类表示二叉查找树的节点，insert函数用于向二叉查找树中插入新节点，build_bst函数则用于根据给定的数组构建二叉查找树。例如，如果我们有以下数组 [5, 3, 7, 2, 4, 6, 8]，调用build_bst函数将返回一个对应的二叉查找树。

二叉查找树的遍历

二叉查找树的遍历方法主要有三种：前序遍历、中序遍历和后序遍历。下面是这三种遍历方法的Python代码实现：

• 前序遍历（Preorder Traversal）：先访问根节点，然后遍历左子树，最后遍历右子树。
• 中序遍历（Inorder Traversal）：先遍历左子树，然后访问根节点，最后遍历右子树。
• 后序遍历（Postorder Traversal）：先遍历左子树，然后遍历右子树，最后访问根节点。
  ```python
  def preorder_traversal(root):
  if root is None:

    return []

  result = [root.val]
  result.extend(preorder_traversal(root.left))
  result.extend(preorder_traversal(root.right))
  return result

def inorder_traversal(root):
result = []
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
result.append(node.val)
node = node.right
return result
```