题解 | #二叉排序树#

#include <iostream>
#include <cstdio>
using namespace std;

struct TreeNode{
    int data;
    TreeNode *leftChild;
    TreeNode *rightChild;
};

/**
 * 二叉搜索树的插入,每次插入返回父节点的data，如果没有父节点则返回-1
 * @param data 插入的数据
 * @param root 该树的根结点
 */
void insertBST(int data, TreeNode * &root){
    TreeNode *treeNode = new TreeNode;
    treeNode->data = data;
    treeNode->rightChild = NULL;
    treeNode->leftChild = NULL;
    if(root == NULL){ //初始树为空
        root = treeNode;
        printf("-1\n");
    }else{ //往左边或者右边搜索
        TreeNode *curNode = root;
        TreeNode *preNode = root;
        while(true){
            int curData = curNode->data;
            if(curData > data){ //往左走
                curNode = preNode->leftChild;
                if(curNode == NULL){ //走到最底部了
                    preNode->leftChild = treeNode;
                    printf("%d\n", preNode->data);
                    break;
                }else{ //继续往下走
                    preNode = curNode;
                }
            }else{ //往右走
                curNode = preNode->rightChild;
                if(curNode == NULL){ //走到最底部了
                    preNode->rightChild = treeNode;
                    printf("%d\n", preNode->data);
                    break;
                }else{ //继续往下走
                    preNode = curNode;
                }
            }
        }
    }
}

int main() {
    TreeNode *root = NULL;
    int n;
    while(scanf("%d", &n) != EOF){
        int i = 0;
        while(i < n){
            int data;
            scanf("%d", &data);
            insertBST(data, root);                 
            i++;
        }
    }
}