题解 | #二叉排序树#

#include <iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
//本题理解题意错误
//错误理解：建立二叉排序树时要添加重复节点，但输出时不用
//正确理解：添加时都不用，满头大汗，什么叫不用输出啊，直接说不插入重复值不就行了，这出题水平快赶上24年408出题老头了
using namespace std;
typedef struct Binode {
    int data;
    struct Binode* lchild;
    struct Binode* rchild;
    Binode(int x): data(x), lchild(NULL), rchild(NULL) {}
};
Binode* buildTree(Binode* root, int x) {
    if (root == NULL) {
        Binode* node = new Binode(x);
        root = node;
    } else if (x > root->data) {
//        if(root->rchild!=NULL)  cout<<"下面将要遍历："<<root->rchild->data;

        root->rchild = buildTree(root->rchild, x);

    } else if (x < root->data) {
//            if(root->rchild!=NULL)  cout<<"下面将要遍历："<<root->lchild->data;
        root->lchild = buildTree(root->lchild, x);
    }
    return root;
}

void preVisit(Binode* root) {
    if (root == NULL) return;
    cout << root->data << " ";
    preVisit(root->lchild);
    preVisit(root->rchild);
}
void midVisit(Binode* root) {
    if (root == NULL) return;
    midVisit(root->lchild);
    cout << root->data << " ";
    midVisit(root->rchild);
}
void postVisit(Binode* root) {
    if (root == NULL) return;
    postVisit(root->lchild );
    postVisit(root->rchild);

    cout << root->data << " ";
}

int main() {
    int sum;
    while (cin >> sum) {
        Binode* root = NULL;
        while (sum > 0) {
            int x;
            scanf("%d", &x);
            root = buildTree(root, x);
            sum--;
        }

        Binode* rootpoint = root;
        preVisit(rootpoint);
        cout << "\n";
        rootpoint = root;
        midVisit(rootpoint);
        cout << "\n";
        rootpoint = root;
        postVisit(rootpoint);
        cout << "\n";
    }
    return 0;
}