推 Asbarla:有，下次我要看題目更仔細些，謝謝你，也謝謝cakeboy大。 10/25 21:54
推 cakeboy:welcome 10/25 22:38
※ 引述《Asbarla (木頭)》之銘言：
: Find all binary trees whose nodes appear in exactly the same sequence in both
: (1) preorder and inorder
: (2) preorder and postorder
: (3) inorder and postorder
: ans:
: 1. 空tree, Root 1個點, 右歪斜的二元樹
: 2. 空tree, Root 1個點
: 3. 空tree, Root 1個點, 左歪斜的二元樹
: 我看不懂解答的意思 我想法是
: 2.給前序跟後序無法決定唯一的B.T -->OK
: 1.給前序跟中序可以決定唯一的B.T，但為什麼說是空的樹呢，
: 而且還有有辦法保證右歪斜嗎?
: 3.給中序跟後序也為什麼可以是左歪斜呢
: 請問有例子可舉嗎?
: 謝謝
他題目意思是說: 要什麼情況下可以讓某棵樹的X序跟X序追蹤法出來的結果一樣
基本上如果樹是空的跟樹只有一個點root的話
用什麼追蹤法都會一樣 所以每個答案都會有空樹跟單純root一個點的樹
(我覺得你好像有點弄錯題目意思)
我先說第一小題跟第三小題 因為這兩小題比較像
第一小題的話
因為前序追蹤樹的順序是中->左->右
中序追蹤樹的順序是左->中->右
因為"中"絕對不可能拿掉(每顆子樹的root,沒了樹就斷了)
因此如果我們讓一棵樹及它的所有子樹的左子樹全空
那麼前序跟中序追蹤起來都會類似 中->右 (因為沒有左了)
舉例:
A
\
C
\
B
\
D
長這樣的右歪斜二元樹
用前序追蹤出來的結果會是ACBD
用中序追蹤出來的結果也是ACBD
如此就可以符合題意
同理所有的右歪斜二元樹都會符合第一小題
至於第三小題
就跟第一小題類似
只是換成中序 (左->中->右)
跟後序 (左->右->中)
同理"中"不能空 因此讓右全空
簡單來說就跟第一題差不多
只是變成了左歪斜二元樹
至於第二小題
照我前面的想法
前序(中->左->右)
後序(左->右->中)
因為"中"不能砍(不能讓樹斷掉)
因此要讓前序跟後序一樣的話
必須讓所有子樹的左子樹跟右樹全空
簡單來說就剩下一個點root的狀況跟空樹的狀況了！
不知道這樣有沒有回答到你的問題。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.139.83
※ 編輯: jameschou 來自: 140.113.139.83 (10/25 17:45)
※ 編輯: jameschou 來自: 140.113.139.83 (10/25 17:45)