题解 | #二叉排序树#

//凡是可以用bst解决的都可以用map解决，map底层为红黑树
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* leftChild;
    TreeNode* rightChild;
};
void insertBST(TreeNode*&  root, int data) {
    TreeNode* pNewNode = new TreeNode;
    pNewNode->data = data;
    pNewNode->leftChild = NULL;
    pNewNode->rightChild = NULL;
    if (root == NULL) {
        root = pNewNode;
        printf("-1\n");
    } else {
        TreeNode* pPre = root; //当前结点的父亲
        TreeNode* pCur; //临时指针
        while (true) {
            //要插入的结点比当前结点的值小
            if (data < pPre->data) {
                //用临时指针往左查
                pCur = pPre->leftChild;
                //临时指针发现父指针没有左孩子 那就插在这
                if (pCur == NULL) {
                    pPre->leftChild = pNewNode;
                    printf("%d\n", pPre->data);
                    break;//结束循环
                } else {
                    //有左孩子，将父节点下移，进入下一轮循环
                    pPre = pCur;
                }
            }
            //要插入的结点比当前结点的值大或等于
            else {
                // 用临时指针往右查
                pCur = pPre->rightChild;
                //临时指针发现父指针没有右孩子 那就插在这
                if (pCur == NULL) {
                    pPre->rightChild = pNewNode;
                    printf("%d\n", pPre->data);
                    break;
                } else {
                    //有右孩子，将父节点下移，进入下一轮循环
                    pPre = pCur;
                }
            }
        }
    }
}


int main() {
    TreeNode* root = NULL;
    int n;
    while (scanf("%d", &n) != EOF) {
        int arrayList[105];
        for (int i = 0; i < n; i++) {
            int num;
            scanf("%d", &num);
            insertBST(root, num);
        }
    }
    return 0;
}