题解 | 二叉排序树

#include <iostream>
using namespace std;

struct tnode {
    struct tnode* l;
    struct tnode* r;
    int val;
};

// 初始化节点
struct tnode* initNode(int a) {
    auto* tmp = (struct tnode*) malloc(sizeof(struct tnode));
    tmp->l = nullptr;
    tmp->r = nullptr;
    tmp->val = a;
    return tmp;
}

// 插入节点到二叉搜索树
int addT(struct tnode* p, int child) {
    // 如果树为空，创建新节点并插入
    if (p == nullptr) {
        auto* newNode = initNode(child);
        return newNode->val;  // 返回新插入的节点的值
    }
    
    // 根据二叉搜索树的性质递归插入
    if (child < p->val) {
        if (p->l == nullptr) {
            p->l = initNode(child);
            return p->val;
        } else {
            return addT(p->l, child);  // 递归插入左子树
        }
    } else {
        if (p->r == nullptr) {
            p->r = initNode(child);
            return p->val;
        } else {
            return addT(p->r, child);  // 递归插入右子树
        }
    }
}

int main() {
    int N;
    struct tnode* root = nullptr;
    
    while (cin >> N) { // 处理多个测试用例
        for (int i = 0; i < N; i++) {
            int num;
            cin >> num;
            if (root == nullptr) {
                root = initNode(num);
                printf("-1\n");  // 第一个节点插入时输出 -1
            } else {
                printf("%d\n", addT(root, num));  // 插入时输出父节点值
            }
        }
    }
    return 0;
}