实验6_2 构造二叉检索树

好的，实验6_2是构造二叉搜索树的实验。二叉搜索树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，而右子树中的所有节点的值都大于根节点的值。这个特性使得二叉搜索树非常适合用于查找操作。

下面是构造二叉搜索树的基本步骤：

1. 创建一个空树，或者从一个节点开始构建。
2. 依次将每个节点插入到树中，直到所有节点都被插入。
3. 对于每个节点，将它与当前节点进行比较，并根据比较结果决定将它插入到左子树或右子树中。
4. 重复步骤3，直到所有节点都被插入到树中。

以下是 Python 代码实现：

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

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

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        node = self.root
        while node:
            if val < node.val:
                if not node.left:
                    node.left = TreeNode(val)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = TreeNode(val)
                    return
                node = node.right

    def inorder(self, node):
        if not node:
            return
        self.inorder(node.left)
        print(node.val, end=' ')
        self.inorder(node.right)

values = [5, 3, 7, 2, 4, 6, 8]
bst = BST()
for val in values:
    bst.insert(val)

bst.inorder(bst.root)  # 输出：2 3 4 5 6 7 8

这个实现中，我们首先定义了一个节点类 TreeNode，它有一个值属性 val，以及左右子节点属性 left 和 right。然后我们定义了二叉搜索树类 BST，它有一个根节点属性 root，以及 insert 和 inorder 两个方法。insert 方法用于插入节点，inorder 方法用于中序遍历树，并输出节点值。

在 insert 方法中，我们首先判断树是否为空，如果是，则将第一个节点作为根节点。如果树不为空，则从根节点开始比较，如果待插入的值小于当前节点的值，则继续比较左子节点，否则继续比较右子节点，直到找到一个空位置插入节点。

在 inorder 方法中，我们先递归遍历左子树，然后输出当前节点的值，最后递归遍历右子树。

最后，我们创建一个 BST 对象，然后依次插入节点，最后中序遍历树并输出节点值。