【C++从练气到飞升】16---二叉搜索树

#include <iostream>
using namespace std;
 
struct Node {
    int key;
    Node *left, *right;
 
    Node(int val) : key(val), left(nullptr), right(nullptr) {}
};
 
class BinarySearchTree {
    Node *root;
 
    Node* insert(Node* node, int key) {
        if (node == nullptr) {
            return new Node(key);
        }
 
        if (key < node->key) {
            node->left = insert(node->left, key);
        } else if (key > node->key) {
            node->right = insert(node->right, key);
        }
 
        return node;
    }
 
    void inorder(Node* node) {
        if (node == nullptr) {
            return;
        }
        inorder(node->left);
        cout << node->key << " ";
        inorder(node->right);
    }
 
public:
    BinarySearchTree() : root(nullptr) {}
 
    void insert(int key) {
        root = insert(root, key);
    }
 
    void inorder() {
        inorder(root);
        cout << endl;
    }
};
 
int main() {
    BinarySearchTree bst;
    bst.insert(5);
    bst.insert(3);
    bst.insert(8);
    bst.insert(1);
    bst.insert(4);
    bst.insert(7);
    bst.insert(6);
    bst.insert(9);
 
    bst.inorder();
    return 0;
}

这段代码定义了一个简单的二叉搜索树类，并在main函数中演示了如何插入和中序遍历这棵树。它提供了二叉搜索树的基本操作，并且是理解二叉搜索树和递归遍历的一个很好的起点。