题解 | #二叉排序树#

#include <stdio.h>
#include <stdlib.h>
typedef struct tnode {
    int x;
    struct tnode* lchild;
    struct tnode* rchild;
} node, *pnode;
void creat_find(int n) {
    pnode r;
    pnode root = malloc(sizeof(node));//创建根节点
    r = root;
    scanf("%d", &root->x);//初始化根节点
    root->lchild = NULL;
    root->rchild = NULL;
    printf("-1\n");//根节点父亲节点-1
    while (n > 1) {
        pnode a = malloc(sizeof(node));//创建新的节点
        scanf("%d", &a->x);//初始化
        a->lchild = NULL;
        a->rchild = NULL;
        while (1) {
            if (a->x > r->x) {//寻找右子树插入
                if (r->rchild == NULL) {//若节点右指针为空，则找到插入节点
                    printf("%d\n", r->x);//该节点的值，即为新插入节点的父亲节点
                    r->rchild = a;//插入
                    r = root;//r重新指向根节点，在下次插入节点时重新从根节点出发寻找插入节点
                    break;
                } else//若有指针不为空，继续向下寻找
                    r = r->rchild;
            } else {//寻找左子树插入，过程同上
                if (r->lchild == NULL) {
                    printf("%d\n", r->x);
                    r->lchild = a;
                    r = root;
                    break;
                } else
                    r = r->lchild;
            }
        }
        n--;
    }
}
int main() {
    int n;
    scanf("%d", &n);
    creat_find(n);
    return 0;
}