用C++构建排序二叉树

排序二叉树（Binary Search Tree）是一种特殊的二叉树，它的左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点。由于其特殊的性质，排序二叉树可以快速地进行查找、插入和删除等操作。下面我将介绍如何使用 C++ 构建排序二叉树。

首先，我们定义一个节点类，用于表示排序二叉树中的一个节点。节点类包含三个成员变量：`value` 表示节点的值，`left` 表示左子树的指针，`right` 表示右子树的指针。

class Node {
public:
    int value;
    Node* left;
    Node* right;
    Node(int val) : value(val), left(NULL), right(NULL) {}
};

接下来，我们定义一个二叉树类，用于表示排序二叉树。二叉树类包含一个指向根节点的指针，以及一些操作函数，包括插入、删除、查找、遍历等操作。

class BinarySearchTree {
public:
    Node* root;
    BinarySearchTree() : root(NULL) {}

    // 插入节点
    void insert(int value) {
        root = insertNode(root, value);
    }

    // 删除节点
    void remove(int value) {
        root = removeNode(root, value);
    }

    // 查找节点
    bool search(int value) {
        return searchNode(root, value);
    }

    // 中序遍历
    void inorderTraversal() {
        inorder(root);
    }

private:
    // 插入节点（内部函数）
    Node* insertNode(Node* node, int value) {
        if (node == NULL) {
            return new Node(value);
        }
        if (value < node->value) {
            node->left = insertNode(node->left, value);
        } else {
            node->right = insertNode(node->right, value);
        }
        return node;
    }

    // 删除节点（内部函数）
    Node* removeNode(Node* node, int value) {
        if (node == NULL) {
            return NULL;
        }
        if (value < node->value) {
            node->left = removeNode(node->left, value);
        } else if (value > node->value) {
            node->right = removeNode(node->right, value);
        } else {
            if (node->left == NULL && node->right == NULL) {
                delete node;
                return NULL;
            } else if (node->left == NULL) {
                Node* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == NULL) {
                Node* temp = node->left;
                delete node;
                return temp;
            } else {
                Node* temp = findMin(node->right);
                node->value = temp->value;
                node->right = removeNode(node->right, temp->value);
            }
        }
        return node;
    }

    // 查找节点（内部函数）
    bool searchNode(Node* node, int value) {
        if (node == NULL) {
            return false;
        }
        if (value < node->value) {
            return searchNode(node->left, value);
        } else if (value > node->value) {
            return searchNode(node->right, value);
        } else {
            return true;
        }
    }

    // 寻找最小节点（内部函数）
    Node* findMin(Node* node) {
        while (node->left != NULL) {
            node = node->left;
        }
        return node;
    }

    // 中序遍历（内部函数）
    void inorder(Node* node) {
        if (node == NULL) {
            return;
        }
        inorder(node->left);
        cout << node->value << " ";
        inorder(node->right);
    }
};

以上就是用 C++ 构建排序二叉树的完整代码。我们可以使用下面的代码对排序二叉树进行测试。

int main() {
    BinarySearchTree bst;

    // 插入节点
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(1);
    bst.insert(4);
    bst.insert(6);
    bst.insert(8);

    // 中序遍历
    bst.inorderTraversal();

    // 查找节点
    cout << endl << bst.search(4) << endl;
    cout << bst.search(9) << endl;

    // 删除节点
    bst.remove(3);
    bst.inorderTraversal();

    return 0;
}

输出结果如下：

1 3 4 5 6 7 8 
1
0
1 4 5 6 7 8 

可以看到，排序二叉树的插入、删除、查找和遍历等操作都可以正常进行。