题解 | 二叉排序树

注意传入的树结点要加引用，而且单根不为空时，是在父结点的左或右孩子位置插入新结点，故必须记录当前结点的父结点。

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

typedef struct LNode {
    int data;
    struct LNode* left;
    struct LNode* right;
} TreeNode, *BiTree;

void insertBST(BiTree& root, int data) { //树一定要传入引用数据类型
    //新建一个树结点
    TreeNode* p = new TreeNode;
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    TreeNode* pre = new TreeNode;
    TreeNode* cur = new TreeNode;
    //若此时根为空，则树结点为根
    if (root == NULL) {
        root = p;
        printf("-1\n");
    } else {
        cur = root;//当前结点
        while (1) {
            //若此时根不空且data大于根值，找到根右边空的位置插入
            if (data > cur->data) {
                pre = cur;
                cur = cur->right;
                if (cur == NULL) {
                    pre->right = p;
                    printf("%d\n", pre->data);
                    break;
                }
            } else {
                //若此时根不空且data小于根值，找到根左边空的位置插入
                pre = cur;
                cur = cur->left;
                if (cur == NULL) {
                    pre->left = p;
                    printf("%d\n", pre->data);
                    break;
                }
            }


        }


    }
}
int main() {
    int N, data;
    BiTree root = NULL;//初始化空树
    while (scanf("%d", &N) != EOF) {
        while (N--) {
            scanf("%d", &data);
            insertBST(root, data);
        }
    }
    return 0;
}