题解 | 二叉排序树

#include <iostream>
using namespace std;

typedef struct Node {
    int data;
    Node* lchild, *rchild;
} Node;

void create(Node*& node, int data = -1) {
    node = new Node();
    node->data = data;
    node->lchild = node->rchild = NULL;
}

void build(Node* head, int data) {
    if (head->data < 0) {
        head->data = data;
        return;
    }
    if (data < head->data) {
        if (head->lchild == NULL) {
            Node* Temp;
            create(Temp, data);
            head->lchild = Temp;
        } else {
            build(head->lchild, data);
        }
    } else if(data == head->data){
        return;
    }else{
        if (head->rchild == NULL) {
            Node* Temp;
            create(Temp, data);
            head->rchild = Temp;
        } else {
            build(head->rchild, data);
        }
    }
}

void preOrder(Node *node, int pre){
    if(node == NULL)
        return;
    if(node->data != pre) cout << node->data << " ";
    preOrder(node->lchild, pre);
    preOrder(node->rchild, pre);    
}

void midOrder(Node *node, int pre){
    if(node == NULL)
        return;
    midOrder(node->lchild, pre);
    if(node->data != pre) cout << node->data << " ";
    midOrder(node->rchild, pre);    
}

void postOrder(Node *node, int pre){
    if(node == NULL)
        return;
    postOrder(node->lchild, pre);
    postOrder(node->rchild, pre);  
    if(node->data != pre) cout << node->data << " ";  
}

int main() {
    int n, data;
    while (cin >> n) {
        Node* head;
        create(head);
        // 建立二叉排序树
        for (int i = 0; i < n; i++) {
            cin >> data;
            build(head, data);
        }
        // 前序遍历
        preOrder(head, -1);
        cout << endl;
        // 中序遍历
        midOrder(head, -1);
        cout << endl;
        // 后序遍历
        postOrder(head, -1);
        cout << endl;
    }
}