[課業] 104年中鋼 資訊工程

[jiangss (struggle)]

104年 中鋼 資訊工程考題，複選題之中，

( ABCDE ) 36.若給予三個節點 A, B, C，哪些是正確的?
(A) 可構成30顆不同的binarytree
(B) 可構成 12 顆不同的 ordered tree
(C) 可構成 9 顆不同的 unordered tree(又稱為 oriented tree)
(D) 可構成 3 顆不同的 free tree(即 connected acyclic graph)
(E) 若三個節點的前序追蹤、中序追蹤或後序追蹤為:ABC，可構成 5 顆不同的
binary tree

請問選項A到D要怎麼解？是否有高手可以提點，
我只知道選項E的公式，謝謝。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.1.90
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1553598166.A.28A.html
推 mage594088: https://imgur.com/a/ISreRxt
→ mage594088: 有錯還請指正~
→ mage594088: 上面網址內共有1文字說明+3張圖A,B,D的圖示哦~
→ mage594088: 突然發現如果答案D也正確的話，定義我要再查一下QQ
推 mage594088: https://goo.gl/PnXXmN
→ mage594088: 上面網頁內有詳解，與解答都一樣了~
→ sm02188612: 先不填ABC值，用三空值節點先建樹結構，而二元樹子節
→ sm02188612: 點有分左右，一般樹沒分。所以三層結構下，二元樹有
→ sm02188612: 先走左(右)再走右(左) 當四種，而一般樹只有每層各一
→ sm02188612: 節點 這一種。
→ sm02188612: 而兩層結構就都是一種，樹根帶兩子節點。畫完結構再
→ sm02188612: 來分別填ABC進去，二元樹共五種結構，每種各3!填法。
→ sm02188612: 一般樹結構共兩種，且可分有序樹跟無序樹，差別是同
→ sm02188612: 父節點的兄弟節點間有次序差別。三層結構的下因為每節
→ sm02188612: 點頂多一子節點，所以無序有序都一樣，3!=6種填法。
→ sm02188612: 而兩層節構下，樹根有兩子節點，有序無序就有差，有
→ sm02188612: 序有3!種填法。無序只有誰當樹根的差別，3種。所以綜
→ sm02188612: 合，有序樹有3!+3!棵，無序樹3!+3棵。
→ sm02188612: free tree就當連通非循環圖，沒有誰當樹根的概念，三
→ sm02188612: 頂點用兩個邊變連通非循環，兩點degree是1，一點degre
→ sm02188612: e是2，就看degree是2的頂點要擺誰，3種放法。
→ jiangss: 謝謝兩位高手解惑