a binary tree has 10 nodes. The inorder and preorder traversal of the tree are shown below

Preorder: JCBADEFIGH
inorder: ABCEDFJGIH

Please draw the tree

這好像是二元搜尋樹的畫法,有大大'能教一下嗎??
然後還有一題是:
Show the contents of stack S1 and the value of variables x and y after the following algorithm segment is excited.

STACK(S1)
push(S1,5)
push(S1,3)
push(S1,2)
if(not empty(S1)) pop (S1,x)
if(not empty(S1)) pop (S1,y)
push(S1,6)

共 21 則回應

噗,我只認得那些大寫字母怎麼辦....

中原SM女王
照兩種順序跑一跑改一改就好了
這題再問二元樹的走訪
你可以先Google inorder跟preorder
的走訪順序
如果文字看不懂的話,找Youtube看看

(Inorder:左→根→右
Preorder:根→左→右)
b4 認真回答的樣子 真帥
B4 B5 在一起 在一起

中原SM女王
B5 助人為快樂之本 (?

還好妳不是說通通收進後宮
又有多元成家了嗎!!!?

長庚魚尾巴
影片支援,順便練一下印度腔英文



M
b6 (羞羞 不小心歪樓了
b8 我是女的耶.........
哇哇哇哇!!!抱歉!!! 那在一起~~在一起~~~((起哄XD

長庚魚尾巴
還是看不太懂....那第二題的堆疊呢?
第二題是FIFO還是FILO?
解第二題
堆疊
演算法執行階段 堆疊狀態
頂----------------底
第一行
第二行 5
第三行 3,5
第四行 2,3,5
第五行 3,5 -----> x=2
第六行 5 -----> y=3
第七行 6,5
STACK是後進先出

STACK(S1)//宣告堆疊S1
push(S1,5)//PUSH進數字"5"
push(S1,3)//PUSH進數字"3"
push(S1,2)//PUSH進數字"2"
if(not empty(S1)) pop (S1,x)//S1不是空的,所以POP出最後的數字2進變數X裡
if(not empty(S1)) pop (S1,y)//S1不是空的,所以POP出最後的數字3進變數Y裡
push(S1,6)//PUSH進數字"6"

結束後x=2, Y=3
STACK(S1)是:
|6|
|5|
B15 總覺得連教育所的資料結構都好強,果然是電資和台大齊名厲害的交大@@
B16 不是啦,敝所有數位學習組,裡面一半算是資管領域

其實教育所在交大好像是負責盛產正妹的~
嗨 難得看到同校的PO文
你的問題都是資料結構的基礎題目
不知道你是什麼系的?
如果想學的話可以修下學期江老師的資料結構,絕對讓你變高手XD
第一題的解法
這種畫tree的大部分都是用preorder或是postorder配合inorder
解法上從preorder或postorder找root
再到inorder看其左右子樹有誰
並遞迴找下去
以這題為例
題目是preorder
preorder第一個是root
也就是J是root
接著到inorder看
J的右邊的(GIH)都是J的右子樹的東西
J的左邊(ABCEDF)則是J的左子樹的東西
接著兩個分開看
在preorder中ABCEDF的排序為CBADEF
這時候就跟上面判斷root一樣
C這時候是J的左子樹中的root
接下來再到inorder中看
就會發現AB再C的左邊,而EDF再C的右邊
同樣的方式GIH在preorder中的順序為IGH
也就是I是J的左子樹
接著再到inorder中看發現是GIH
也就是G是I的左子樹,H是I的右子樹
整棵樹都是用同樣的方法來找
而如果是postorder的話,則是最後一個為root
然後再到inorder找此root與其他點的相對位置

希望有幫到你囉~
有誤請糾正,感謝><
大家都好強啊…
我剛好也陷在計概的水深火熱之中
上次考試就差計概不然就考上了……
我對這些一竅不通啊QQ
B18 我是營建系的 我是因為要考聯合大學的轉學考然後看不太懂這兩題拿來問的
馬上回應搶第 22 樓...