题解 | 二叉排序树

使用双指针建立二叉排序树，注意以前输入的数据不用再插入到书中，本题依然需要用while循环输入，每次建树前记得把root置为空否则下次再次建树root不为空导致根结点没法初始化

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

// 应对重复元素，建立一个哈希表，若输入的元素出现过，忽略本次插入操作
int hash[1001];

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

void preorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void postorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

int main() {
    int n, x;
    TreeNode* root;
    TreeNode* pre;
    TreeNode* cur;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < 1001; i++) {
            hash[i] = 0;
        }
        root = NULL;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            if (hash[x] == 1) continue;
            hash[x] = 1;
            TreeNode* newnode = new TreeNode;
            newnode->data = x;
            newnode->left = NULL;
            newnode->right = NULL;
            if (root == NULL) {
                root = newnode;
            }
            else {
                pre = root; // 从根开始比较
                cur = root;
                // 二叉排序树一定是在空叶子插入
                while (cur != NULL) {
                    if (x < pre->data) {
                        cur = pre->left;
                        if (cur == NULL) {
                            pre->left = newnode;
                            break;
                        }
                        pre = cur; // 继续找下一个符合条件的位置
                    }
                    if (x > pre->data) {
                        cur = pre->right;
                        if (cur == NULL) {
                            pre->right = newnode;
                            break;
                        }
                        pre = cur; // 继续找下一个符合条件的位置
                    }
                }
            }
        }
        // 输出前中后序遍历
        preorder(root);
        printf("\n");
        inorder(root);
        printf("\n");
        postorder(root);
        printf("\n");
    }
    return 0;
}