二下

資料結構｜HW3

二元樹判斷

題目敘述

題目要求設計一個程式，可以判斷輸入的節點資料是否能構成一棵二元樹。程式會持續接收多組測試資料作為輸入，每組測試資料由若干個節點資訊組成，節點資訊的格式為”(節點值,子節點位置)”。子節點位置用L表示左子節點,R表示右子節點。例如”(5,)”表示節點值為5且沒有子節點，也就是根結點，”(4,L)”表示節點值為4且只有左子節點。

當輸入資料能構成一棵二元樹時，程式需輸出該二元樹的後序遍歷結果。如果輸入資料無法構成一個合理的二元樹，則輸出”wrong data”。

輸入會一直持續到輸入只剩”()”為止，代表測試資料結束。題目也提供了一些輸入輸出的範例加以說明。

答題思路

  • 從樹的底端一層層往上檢查，檢查節點是否存在父節點。
  • 使用Binary Tree Array時，index / 2 即為該節點的父節點。

參考答案 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <climits>

#define nullInt INT_MIN

using namespace std;

void parseInput(string& input, vector<pair<int, string>>& pairs) {
    for(auto& c : input) c = (c == '(' || c == ')') ? '"' : (c == ',') ? ' ' : c;

    istringstream iss1(input);
    string pairStr;
    while(iss1 >> quoted(pairStr)) {
        
        if(!pairStr.compare("")) break;
        
        istringstream iss2(pairStr);
        int idx;
        string str;
        iss2 >> idx >> str;
        pairs.push_back({idx, str});
    }
}

vector<int> createBinaryTree(vector<pair<int, string>>& pairs, int length) {
    vector<int> binaryTree(length, nullInt);

    for(auto & p : pairs) {
        if(!p.second.compare("")) {
            binaryTree[0] = p.first;
            continue;
        }
        int idx = 0;
        for(auto & c : p.second) idx = (idx << 1) + ( c == 'L' ? 1 : 2);
        binaryTree[idx] = p.first;
    }

    return binaryTree;
}

bool checkBinaryTree(vector<int>& binaryTree, size_t branchLevel) {
    if(binaryTree[0] == nullInt) return false;

    // check each level
    size_t left = binaryTree.size() - (1 << branchLevel);
    size_t right = binaryTree.size();
    for(size_t i(branchLevel); i > 0; --i) {
        for(size_t j(left); j < right; ++j) {
            if(binaryTree[j] != nullInt) { // check acestral node
                int idx = (j-1) >> 1;
                if(binaryTree[idx] == nullInt) return false;
            }
        }
        left >>= 1;
        right >>= 1;
    }

    return true;
}

void postOrderTraversal(const vector<int>& binTree, int index) {
    if (index >= binTree.size()) return;
    postOrderTraversal(binTree, 2 * index + 1);
    postOrderTraversal(binTree, 2 * index + 2);
    if(binTree[index] != nullInt) cout << binTree[index] << " ";
}

int main() {
    
    string input;
    while(getline(cin , input) && input != "()" && input != "") {
        vector<pair<int, string>> pairs;
        parseInput(input, pairs);

        auto maxElement = std::max_element(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
            return a.second.length() < b.second.length();
        });

        vector<int> binaryTree = createBinaryTree(pairs, (1 << maxElement->second.length()+1) -1);
        if(!checkBinaryTree(binaryTree, maxElement->second.length())) cout << "wrong data" << endl;
        else {
            postOrderTraversal(binaryTree, 0);
            cout << endl;
        }
    }

    return 0;
}