ZeroJudge D526: Binary Search Tree (BST)

題目敘述

題目採EOF方式收資料，每筆資料第一行有一個正整數N，第二行會有N個整數。要求建立一個二元搜尋樹然後輸出這個二元搜尋樹。

範例輸入

11

368 115 121 88 741 762 801 34 41 511 60

6

5 2 10 4 9 15

範例輸出

368 115 88 34 41 60 121 741 511 762 801

5 2 4 10 9 15

解題思路

建立一個struct，裡面存目前的值和左右兩邊的資料 (如範例程式碼所示)。將資料輸入之後使用For迴圈將資料一個一個進行判斷是否是要塞到資料結構的左邊還是右邊，如果該方向已經有資料了就要判斷是要在這個資料往右還是往左放，可以使用while(true)來進行判斷，將已經存在的資料往左/右邊推一個，因為struct本身裡面的左右兩邊資料也是struct，所以會形成一個無限的迴圈狀態可以一直塞資料。將二元搜尋樹建立完之後可以使用遞迴將最一開始的struct中的資料輸出，如果有左邊的話就一直往左邊輸出，當左邊沒有資料之後再從最下面往回找有沒有要輸出的右邊，以此類推到樹狀圖最右下角。

解題程式碼如下 (僅供參考)：

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

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

void again(Node* hi)
{
    if (hi->left != nullptr)
    {
        cout << hi->left->value << " ";
        again(hi->left);
    }
    if (hi->right != nullptr)
    {
        cout << hi->right->value << " ";
        again(hi->right);
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(nullptr);
    int N;
    while (cin >> N)
    {
        vector<int>a;
        for (int i = 0; i<N; i++)
        {
            int tmp;
            cin >> tmp;
            a.push_back(tmp);
        }
        Node* sean = new Node();
        sean->value = a[0];
        Node* root;
        for(int i = 1; i < N; i++) {
            root = sean;
            Node* p = new Node();
            p->value = a[i];
            while(true) {
                if(root->value < a[i]) {
                    if(root->right == nullptr) {
                        root->right = p;
                        break;
                    } else {
                        root = root->right;
                    }
                }
                else if(root->value > a[i]) {
                    if(root->left == nullptr) {
                        root->left = p;
                        break;
                    } else {
                        root = root->left;
                    }
                }
            }
        }
        cout << sean->value << " ";
        again(sean);
        cout << "\n";
    }
}