题解 | #二叉排序树#

#include <stdio.h>
#include <stdlib.h>


typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node ;

void insert(Node* head, int value) {
    if (value < head->val) {
        if (head->left == NULL) {
            Node* pNew =  (Node*)malloc(sizeof(Node));
            pNew->val = value;
            pNew->left = pNew->right = NULL;
            head->left = pNew;
        } else {
            insert(head->left, value) ;
        }
    } else if(value > head->val){
        if (head->right == NULL) {
            Node* pNew =  (Node*)malloc(sizeof(Node));
            pNew->val = value;
            pNew->left = pNew->right = NULL;
            head->right = pNew;
        } else {
            insert(head->right, value) ;
        }
    }
}

void preOrder(Node *head){
    if(head==NULL){return;}
    printf("%d ",head->val);
    preOrder(head->left);
    preOrder(head->right);
}

void inOrder(Node *head){
    if(head==NULL){return;}
    inOrder(head->left);
    printf("%d ",head->val);
    inOrder(head->right);
}

void postOrder(Node *head){
    if(head==NULL){return;}
    postOrder(head->left);
    postOrder(head->right);
    printf("%d ",head->val);
}

int main() {
    int n;
    while (scanf("%d ", &n) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to
        int value;
        Node* head = (Node*)malloc(sizeof(Node));
        scanf("%d", &head->val);
        head->left = head->right = NULL;
        int cnt = 1;
        while (cnt < n) {
            scanf("%d", &value);
            insert(head, value);
            cnt++;
        }
        preOrder(head);
        printf("\n");
        inOrder(head);
        printf("\n");
        postOrder(head);
        printf("\n");
    }
    return 0;
}