Re: [理工] [資結] 前序後序問題

[kuso0516 (隱)]

※ 引述《kuso0516 (隱)》之銘言：
: 考慮以下程式碼
: void order(node p){
: if(p == NULL) return;
:    order(p->left);
:    cout<<")";
:    order(p->right);
:    cout<<"(";
: }
: 若某二元樹T的order(T)結果為
: )()()))()((())())(((
: 求該二元樹
: 節點可任意命名


話說這是我和我朋友寫資結的時候無聊想到的題目
另開一題
這題比原版的簡單
不過解法的思路不太一樣
我們兩人都覺得這兩題會的話
前中後序就一定沒問題了

不過前中後序本身也沒什麼難度就是了....

題二
考慮以下程式碼
void order(node p){
   static int i=0;
   if(p == NULL) return;
   order(p->left);
   cout<<"*";
   order(p->right);
   cout<<++i;
}
若某二元樹T的order(T)結果為
**12**34***5*678
求該二元樹
節點可任意命名

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.125.33.190
推 AIdrifter:幫推 結果我還是沒辦法像小黃依樣用遞迴硬幹~"~
推 gskman:思路有不一樣嗎 我畫一畫就畫出來了阿@@
→ gskman:還是我又搞錯了XD
推 genius945:我也覺得想法一樣@@"  不過我畫的好慢嗚嗚嗚 死定了
→ kuso0516:這題可以用另一種方式解
首先
編號是障眼法
直接把編號當節點就好
* * 1 2 * * 3 4 * * * 5 * 6 7 8
│└┘││└┘│││└┘└┘││
└──┘└──┘│└────┘│
                └──────┘

忽略星號
12345678就是後序
將編號取代星號
得21438756
就是中序了


當然題一也可以用這種方式
只是題一的精神在於你得知道為什麼定出一個樹一定得要中序
一但瞭解程式碼的來由
不需要編號也可以直接畫出來了
速度很快
→ gskman:怎麼解?
※ 編輯: kuso0516        來自: 122.125.35.190       (11/27 23:52)
→ gskman:哈 我都沒想這麼多直接畫耶XD 還好答案一樣
推 gskman:這個解法比較有趣 要了解程式的意義 有趣的題目
推 genius945:我好弱..Orz  原PO還可以唸書唸到想題目
推 TNC:我題一是自己加上編號去畫XD
→ sneak: 思路有不一樣嗎 我畫一 https://daxiv.com