题解 | 二叉排序树

#include <cstdlib>
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;



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

void inOrder(TreeNode* head) {
    if (head == nullptr) return;
    cout << head->val << " ";
    inOrder(head->left);
    inOrder(head->right);
}

void midOrder(TreeNode* head) {
    if (head == nullptr) return;
    midOrder(head->left);
    cout << head->val << " ";
    midOrder(head->right);
}

void backOrder(TreeNode* head) {
    if (head == nullptr) return;
    backOrder(head->left);
    backOrder(head->right);
    cout << head->val << " ";
}

int main() {
    int n;
    while (cin >> n) {
        TreeNode* head;
        unordered_set<int> set;
        for (int i = 0; i < n; i++) {
            int num;
            cin >> num;
		  
            if (set.find(num) != set.end()) continue;
            else {
                set.insert(num);
            }
		  
            TreeNode* cur = head;
            TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));

            node->left = nullptr;
            node->right = nullptr;
            node->val = num;
            if (i == 0) head = node;
            else {
                while (cur != nullptr) {
                    if (num > cur->val && cur) {
                        if (cur->right == nullptr) {
                            cur->right = node;
                            break;
                        };
                        cur = cur->right;

                    } else if (num < cur->val && cur) {
                        if (cur->left == nullptr) {
                            cur->left = node;
                            break;
                        }
                        cur = cur->left;
                    }
                }

            }
        }
        inOrder(head);
        cout << endl;
        midOrder(head);
        cout << endl;
        backOrder(head);
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")

排序二叉树创建与前序后序中序遍历