二叉排序树建立

1.pic.jpg

#include <iostream>
#include <stdio.h>

using namespace std;

struct node {
    int data;
    node* left;
    node* right;
};

// 注意 root 这里传的是 引用
void insert(node* &root, int x) {
    if(root == NULL) {
        root = new node;
        root->data = x;
        root->left = NULL;
        root->right = NULL;
        return;
    }

    if(root->data == x){
        return;
    } else if(x < root->data) {
        insert(root->left, x);
    } else {
        insert(root->right, x);
    }
}

// 2 1 6 3 5 4 9 7 8 10
void preOrder(node* root) {
    if(root == NULL){
        return;
    }
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 1 4 5 3 8 7 10 9 6 2
void postOrder(node* root) {
    if(root == NULL){
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

// 10
// 2 6 9 3 5 7 10 8 4 1
int main() {
    int n;
    scanf("%d",&n);

    int x;
    node* root = NULL;
    for(int i=0;i<n;i++) {
        scanf("%d", &x);
        insert(root, x);
    }

    preOrder(root);
    printf("\n");
    postOrder(root);

    return 0;
}

非引用写法

node* insert(node* root, int x) {
    if(root == NULL) {
        root = new node;
        root->data = x;
        root->left = NULL;
        root->right = NULL;
        return root;
    }

    if(root->data == x){
        return root;
    } else if(x < root->data) {
        root->left = insert(root->left, x);
    } else {
        root->right = insert(root->right, x);
    }
    return root;
}

node* root = NULL;
for(int i=0;i<n;i++) {
    scanf("%d", &x);
    root = insert(root, x);
}

录了个上传头条的小视频帮助理解 https://pan.baidu.com/s/12GPbJNNtDBif3TkSxoHZJQ