為什麼這篇二元樹走訪題目鄉民發文收入到精華區：因為在二元樹走訪題目這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者m6c04dk4 (飄婆難)看板C_and_CPP標題[問題] 給(前序or後序)+中序,建構為...
目前遇到一個問題
比如說今天題目給了一顆2元樹
前序走訪:CABDEF
中序走訪:BACEDF
還原成2元樹的話應該是長這樣
C
／ ＼
A D
／ ／＼
B E F
用想的是沒問題...
但是題目要求寫出程式碼...
想請問一下
要用什麼資料結構把給前序+中序
建構成二元樹的過程 寫成演算法?
想了很久實在沒有頭緒
有知道的版友可以給個大約的方向嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.138.228
推 LPH66:把你想的邏輯轉化成演算法就好 09/04 20:47
→ diabloevagto:你能用紙筆把流程一步一步寫下來嗎？ 09/04 20:56
可以呀
但是我卡在不知道要用什麼樣的資料結構先去存前序跟中序
比如說
前序第一個一定是樹根
再來去中序找到樹根 2邊就分別是左子樹跟右子樹
如此遞迴找下去
但就是有一種說不上來的沒頭緒...
※ 編輯: m6c04dk4 來自: 111.254.138.228 (09/04 21:11)
→ elenya:看題目要求輸出什麼就建什麼,要樹就給樹,不用額外資料結構 09/04 21:16
→ elenya:前序跟中序,題目給字串就用字串而已... 09/04 21:17
→ AnyaAlstreim:就是不需要額外的資料結構，你的流程可能不夠仔細 09/05 00:49
推 johnjohnlin:首先找出 C (頭)，分成左邊右邊，接著 recursive 作 09/05 14:17
推 longlongint:上下兩組都要切成兩段(左子樹,右子樹) 09/05 23:34
→ longlongint:每次找到新的根的時候加入新點 09/05 23:37
→ longlongint:遞迴函數的參數是 : 前序, 後序 兩個字串 09/05 23:44
→ longlongint:函數運作結果 : 將子樹建出來 09/05 23:44
→ longlongint:建構方式:左子樹，右子樹先建完之後，串到根上 09/05 23:49
→ longlongint:然後回傳整顆樹。 PS: 切字串的時候用長度切 09/05 23:50
→ longlongint:看不懂的話就去解 UVA 536 09/06 00:30
OK 謝謝大大
※ 編輯: m6c04dk4 來自: 111.254.116.91 (09/07 08:15)
→ longlongint:讓我獻醜一下，網路上面找到的Code一定都比我短(淚目 09/15 00:16
→ longlongint:題外話如果你打 AAAAA AAAAA 我的程式無法解決 09/15 00:28