國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

三、一個二元搜尋樹 (Binary search tree) 的前序追蹤 (Preorder traversal) 結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20

    請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree (NODEPTR tree)，輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25分）

#include <iostream>

#include <queue>

using namespace std;

struct node {

    int info;

    struct node* left;

    struct node* right;

};

typedef struct node* NODEPTR;

void sortTree(NODEPTR tree) {

    if (tree != NULL) {

        sortTree(tree->left);

        printf("%d ", tree->info);

        sortTree(tree->right);

    }

}

// 建立節點

void createNode(NODEPTR& t, int data) {

    t = (NODEPTR)malloc(sizeof(NODEPTR));

    t->info = data;

    t->left = NULL;

    t->right = NULL;

}

int main( ) {

    /*                   14

                /               \

               4                 15

          /         \              \

         3           9             18

                    /           /      \

                   7           16       20

                  /             \

                 5              17

    */

    NODEPTR root = NULL;

    createNode(root, 14);

    createNode(root->left, 4);

    createNode(root->right, 15);

    createNode(root->left->left, 3);

    createNode(root->left->right, 9);

    createNode(root->right->right, 18);

    createNode(root->left->right->left, 7);

    createNode(root->right->right->left, 16);

    createNode(root->right->right->right, 20);

    createNode(root->left->right->left->left, 5);

    createNode(root->right->right->left->right, 17);

    sortTree(root);

    return 0;

}