题解 | #二叉排序树#

//关于父节点可采用链表中pre和rear指针的思想，采用正常的循环即可
#include "stdio.h"
using namespace std;
struct TreeNode{
    int data;
    TreeNode *leftChild;
    TreeNode *rightChild;
};
void insertBST(TreeNode * &root,int data){
    TreeNode *node = new TreeNode;//建在堆中
    node->data = data;
    node->leftChild = NULL;
    node->rightChild = NULL;
    if(root == NULL){
        root = node;
        printf("%d\n",-1);
    } else{
        TreeNode *pre;
        TreeNode *pos;
        pos = root;
        bool flag = true;
        while (pos != NULL){
            if(pos->data > data){
                pre = pos;
                pos = pos->leftChild;
                flag = true;
            } else{
                pre = pos;
                pos = pos->rightChild;
                flag = false;
            }
        }
        if(flag)
            pre->leftChild = node;
        else
            pre->rightChild = node;
        printf("%d\n",pre->data);
    }
}

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