题解 | #二叉排序树#

难点在于二叉树插入节点的递归处理

#include <iostream>
using namespace std;
struct treeNode {
    int data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(int i) {
        data = i;
        leftChild = NULL;
        rightChild = NULL;
    }
};
treeNode* insert(treeNode* root, int i) {
    if (root == NULL) {
        root = new treeNode(i);
    } else if (i < root->data) {
        root->leftChild = insert(root->leftChild, i);
    } else if (i > root->data) {
        root->rightChild = insert(root->rightChild, i);
    }
    return root;
}
void preOrder(treeNode* root) {
    if (root == NULL) return;
    cout << root->data << ' ' ;
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}
void inOrder(treeNode* root) {
    if (root == NULL) return;
    inOrder(root->leftChild);
    cout << root->data << ' ' ;

    inOrder(root->rightChild);
}
void postOrder(treeNode* root) {
    if (root == NULL) return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->data << ' ' ;

}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        treeNode* root = NULL;
        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            root = insert(root, temp);
        }
        preOrder(root);
        cout << endl;
        inOrder(root);
        cout << endl;
        postOrder(root);
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")