题解 | #二叉排序树#

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct tree {
    int a;
    struct tree* lchild;
    struct tree* rchild;
    struct tree* parent;
} tree;
int main() {
    int n;
    scanf("%d", &n);
    int a[100];
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        a[i] = temp;
    }
    struct tree T;
    T.a = a[0];
    T.lchild = NULL;
    T.rchild = NULL;
    T.parent = NULL;
    printf("%d\n", -1);

    struct tree* temp = &T;
    for (int i = 1; i < n; i++) {
        struct tree* tempnode = (tree*)malloc(sizeof(tree));
        tempnode->a = a[i];
        tempnode->lchild = NULL;
        tempnode->rchild = NULL;
        tempnode->parent = NULL;
        while (1) {
            if (temp->a < a[i] && temp->rchild == NULL) {
                temp->rchild = tempnode;
                tempnode->parent = temp;
                printf("%d\n", tempnode->parent->a);
                break;
            } else if (temp->a > a[i] && temp->lchild == NULL) {
                temp->lchild = tempnode;
                tempnode->parent = temp;
                printf("%d\n", tempnode->parent->a);
                break;
            } else if (temp->a < a[i]) {
                temp = temp->rchild;
            } else {
                temp = temp->lchild;
            }
        }
        temp = &T;
    }
    return 0;
}