ZeroJudge D526: Binary Search Tree (BST)

將下列建值輸入，直接建立一個二元搜尋樹， 368、115、121、88、741、762、801、34、41、511、60。欲找建值為34的節點，從368節點為第一次起算，需要做幾次比較 ? 

只是想請你建出一個二元搜尋樹，並輸出此樹的前序搜尋 (中、左、右)。

範例測資

範例輸入範例輸出
EOF 輸入，第一行有一個數字 N (1 ≦ N ≦ 1000)。
第二行會建入 N 個數字 M (1 ≦ M ≦231-1) ，且沒有數字會重複。		輸出該樹的前序搜尋結果。
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，裡面存目前的值和左右兩邊的資料 (Value、Left、Right)。將資料輸入之後使用For迴圈將資料一個一個進行判斷是否是要塞到資料結構的左邊還是右邊，如果該方向已經有資料了就要判斷是要在這個資料往右還是往左放，可以使用while(true)來進行判斷，將已經存在的資料往左/右邊推一個，因為Struct本身裡面的左右兩邊資料也是Struct，所以會形成一個無限的迴圈狀態可以一直塞資料。將二元搜尋樹建立完之後可以使用遞迴將最一開始的Struct中的資料輸出，如果有左邊的話就一直往左邊輸出，當左邊沒有資料之後再從最下面往回找有沒有要輸出的右邊，以此類推到樹狀圖最右下角。

範例程式碼－ZeroJudge D526: Binary Search Tree (BST)

#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";
    }
}

//ZeroJudge D526
//Dr. SeanXD
標籤

相關文章

發佈留言