题解 | #二叉排序树#

#include <cstdio>
#include <iostream>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* leftChild;
    TreeNode* rightChild;
};

void buildBST(TreeNode*& root, int data) {
    TreeNode *treeNode = new TreeNode; //在堆上新建结点
    treeNode->data = data;
    treeNode->leftChild = NULL;
    treeNode->rightChild = NULL;
    if(root == NULL){
        root = treeNode;
        return;
    }
    TreeNode *curNode = root;
    TreeNode *preNode = root;
    
    while(true){ 
        if(data > curNode->data){ //往右走
            preNode = curNode;
            curNode = curNode->rightChild;
            if(curNode == NULL){
                preNode->rightChild = treeNode;
                //curNode = treeNode; 这种写法是错误的
                break;
            }
        }else if(data < curNode->data){ //往左走
            preNode = curNode;
            curNode = curNode->leftChild;
            if(curNode == NULL){
                preNode->leftChild = treeNode;
                //curNode = treeNode;
                break;
            }
        }else{ //相同的元素，忽略
            break;
        }
    }
}

void PreOrder(TreeNode* treeNode) {
    if (treeNode == NULL) {
        return;
    }
    printf("%d ", treeNode->data);
    PreOrder(treeNode->leftChild);
    PreOrder(treeNode->rightChild);
}

void InOrder(TreeNode* treeNode) {
    if (treeNode == NULL) {
        return;
    }
    InOrder(treeNode->leftChild);
    printf("%d ", treeNode->data);
    InOrder(treeNode->rightChild);
}

void PostOrder(TreeNode* treeNode) {
    if (treeNode == NULL) {
        return;
    }
    PostOrder(treeNode->leftChild);
    PostOrder(treeNode->rightChild);
    printf("%d ", treeNode->data);
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        TreeNode* treeNode = NULL;
        int data;
        for (int i = 0; i < n; i++) {
            scanf("%d", &data);
            buildBST(treeNode, data);
        }
        PreOrder(treeNode);
        printf("\n");
        InOrder(treeNode);
        printf("\n");
        PostOrder(treeNode);
        printf("\n");
    }
}
// 64 位输出请用 printf("%lld")