二叉查找树的构造与遍历

二叉查找树（BST）是一种常用的数据结构，它的每个节点最多有两个子节点，且左子节点的值小于等于父节点的值，右子节点的值大于父节点的值。BST的构造方法有很多种，其中一种常用的方法是插入节点。具体步骤如下：

1. 如果BST为空，则插入的节点成为根节点。
2. 如果插入的节点值小于根节点的值，则递归地插入到左子树中。
3. 如果插入的节点值大于根节点的值，则递归地插入到右子树中。
4. 如果插入的节点值等于根节点的值，则不插入。

遍历BST有三种方法：前序遍历、中序遍历和后序遍历。其中，前序遍历的顺序是根节点、左子树、右子树；中序遍历的顺序是左子树、根节点、右子树；后序遍历的顺序是左子树、右子树、根节点。遍历的具体实现可以使用递归或迭代的方法。以下是使用递归实现的代码示例：

// 定义BST节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// BST插入节点
TreeNode* insertNode(TreeNode* root, int val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else if (val > root->val) {
        root->right = insertNode(root->right, val);
    }
    return root;
}

// BST前序遍历
void preOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// BST中序遍历
void inOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// BST后序遍历
void postOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}