C++中二叉排序树的定义、构造及其遍历

二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的每个节点都满足以下性质：

1. 左子树上所有节点的值都小于它的根节点的值。

2. 右子树上所有节点的值都大于它的根节点的值。

3. 左右子树都是二叉排序树。

因此，二叉排序树的中序遍历可以得到一个递增的有序序列。

二叉排序树的构造可以通过插入节点来实现。具体地，对于待插入的节点，从根节点开始比较它的值与当前节点的值的大小关系，若小于当前节点的值，则继续在当前节点的左子树上进行比较，若大于当前节点的值，则继续在当前节点的右子树上进行比较，直到找到一个空节点，将待插入的节点插入到该位置。

下面是一个简单的示意图，表示一个二叉排序树：

         6
        / \\
       4   8
      / \\ / \\
     3  5 7  9

在这个示意图中，树的根节点是 6，它有两个子节点 4 和 8，分别对应左子树和右子树。在左子树中，4 又有两个子节点 3 和 5。在右子树中，8 又有两个子节点 7 和 9。这个二叉排序树中，所有左子节点的值都小于它们的父节点的值，所有右子节点的值都大于它们的父节点的值。

二叉排序树的遍历包括前序遍历、中序遍历和后序遍历。其中，中序遍历是最常用的一种遍历方式，可以得到一个有序的序列。

下面是C++中二叉排序树的代码实现：

// 二叉排序树的节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 向二叉排序树中插入节点
void insert(TreeNode *&root, int val) {
    if (root == nullptr) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insert(root->left, val);
    } else {
        insert(root->right, val);
    }
}

// 中序遍历二叉排序树
void inorderTraversal(TreeNode *root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

可以通过调用insert函数向二叉排序树中插入节点，通过调用inorderTraversal函数进行中序遍历。

中序遍历的代码实现如下：

void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

前序遍历的代码实现如下：

void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

后序遍历的代码实现如下：

void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

其中，TreeNode 是二叉排序树的结点类型，其定义如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

构造二叉排序树的过程中，对于每个结点，将其插入到二叉排序树中的代码实现如下：

void insert(TreeNode*& root, int val) {
    if (root == nullptr) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insert(root->left, val);
    } else if (val > root->val) {
        insert(root->right, val);
    }
}

其中，root 是指向当前子树根结点的指针的引用，val 是要插入的值。

最后，对于一个二叉排序树，我们可以按照中序遍历的顺序，得到一个升序排列的数组。遍历代码如下：

void inorder(TreeNode* root, vector<int>& nums) {
    if (root == nullptr) return;
    inorder(root->left, nums);
    nums.push_back(root->val);
    inorder(root->right, nums);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> nums;
    inorder(root, nums);
    return nums;
}

其中，nums 是存储遍历结果的数组。

二叉排序树的删除操作比较复杂，分为三种情况：

1. 被删除节点没有子节点，即为叶子节点，直接删除即可。

2. 被删除节点只有一个子节点，将该子节点与被删除节点的父节点相连即可。

3. 被删除节点有两个子节点，需要找到被删除节点的中序遍历的前驱或后继节点来替代被删除节点，然后再将该前驱或后继节点删除。

具体步骤如下：

1. 在二叉排序树中查找要删除的节点。

2. 如果要删除的节点为叶子节点或只有一个子节点，则直接删除该节点。

3. 如果要删除的节点有两个子节点，则找到它的中序遍历的前驱或后继节点，用该节点替代要删除的节点，然后删除前驱或后继节点。

4. 删除节点后需要调整二叉排序树，保持其特性。

下面是C++实现二叉排序树删除节点的代码示例：

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) {
        return nullptr;
    }
    if (root->val == key) {
        if (!root->left) {
            return root->right;
        }
        if (!root->right) {
            return root->left;
        }
        TreeNode* cur = root->left;
        while (cur->right) {
            cur = cur->right;
        }
        cur->right = root->right;
        return root->left;
    }
    if (root->val > key) {
        root->left = deleteNode(root->left, key);
    } else {
        root->right = deleteNode(root->right, key);
    }
    return root;
}

该函数使用递归实现，首先查找要删除的节点，然后分情况讨论：

1. 如果要删除的节点没有子节点或只有一个子节点，则直接删除该节点，并返回其子节点。

2. 如果要删除的节点有两个子节点，则找到其中序遍历的前驱或后继节点，将其值赋给当前节点，然后递归地删除前驱或后继节点。

删除节点后，还需要调整二叉排序树，保持其特性，具体实现可以参考插入操作中的调整过程。

二叉排序树的删除操作分为三种情况：

1. 要删除的节点没有左右子树，直接删除即可。

2. 要删除的节点有一个子树，将该节点的父节点指向该节点的子节点即可。

3. 要删除的节点有两个子树，此时需要找到该节点的前驱或后继节点来替代该节点。具体步骤如下：

• 如果该节点有右子树，则其后继节点为右子树中最小的节点，即右子树的最左节点，用后继节点的值替换要删除的节点的值，再将删除操作转化为删除后继节点。

• 如果该节点没有右子树，但有左子树，则其前驱节点为左子树中最大的节点，即左子树的最右节点，用前驱节点的值替换要删除的节点的值，再将删除操作转化为删除前驱节点。

• 如果该节点既没有左子树也没有右子树，则可以直接删除。

删除操作的实现代码如下：

Node* deleteNode(Node* root, int key) {
    if (root == NULL) {
        return NULL;
    }
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            Node* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            delete root;
            return temp;
        } else {
            Node* successor = root->right;
            while (successor->left != NULL) {
                successor = successor->left;
            }
            root->val = successor->val;
            root->right = deleteNode(root->right, successor->val);
        }
    }
    return root;
}

二叉排序树的遍历和普通二叉树的遍历方式一样，可以使用前序、中序、后序遍历进行遍历。此外，二叉排序树还可以使用中序遍历得到有序序列。