UVa12347 - Binary Search Tree(遞迴)

題目大意

給你前序二元樹，請輸出後序二元樹

題目連結

分析

• 由於這種二元樹並不是平衡二元樹，因此這邊如果是完全左傾二元樹，long long 說不定都裝不下 index
• 因此這邊用 linklist 去實踐二元樹會更好
• 他使用 cin 好像會怪怪的，因此建議用 scanf

參考連結

UVa12347 - Binary Search Tree(遞迴) by Programming學習筆記

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200000
//#define int long long
using namespace std;
int num[MAXN];

struct treeLink{
    int value = 0;
    treeLink* Lnode = nullptr;
    treeLink* Rnode = nullptr;
}Stree; //single tree


void update(treeLink* &root, int a){ //root 必須是 by ref

    if(root == nullptr){
        root = new treeLink;
        root->value = a;
        root->Lnode = nullptr;
        root->Rnode = nullptr;

        return;
    }
    //cout << "root " << root->value << "\n";
    if(a < root->value) update(root->Lnode, a);
    if(a > root->value) update(root->Rnode, a);
}

void post_print(treeLink *root){
    if(root != nullptr){
        post_print(root->Lnode);
        post_print(root->Rnode);
    }
    if(root != nullptr) cout << root->value << "\n";
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r",  stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    int len = 1;
    while(scanf("%d", &num[len]) == 1){
        len++;
    }
    //cout << "len " << len << "\n";
    treeLink *tree = nullptr; //當你要給它資料時記得必須 constructor

    for(int i = 1; i < len ; i++) update(tree, num[i]);
    post_print(tree);

    return 0;
}