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的公式，謝謝。

" target="_blank" rel="nofollow">

有錯還請指正~上面網址內共有1文字說明+3張圖A,B,D的圖示哦~突然發現如果答案D也正確的話，定義我要再查一下QQhttps://goo.gl/PnXXmN上面網頁內有詳解，與解答都一樣了~

先不填ABC值，用三空值節點先建樹結構，而二元樹子節點有分左右，一般樹沒分。所以三層結構下，二元樹有先走左(右)再走右(左) 當四種，而一般樹只有每層各一節點 這一種。而兩層結構就都是一種，樹根帶兩子節點。畫完結構再來分別填ABC進去，二元樹共五種結構，每種各3!填法。一般樹結構共兩種，且可分有序樹跟無序樹，差別是同父節點的兄弟節點間有次序差別。三層結構的下因為每節點頂多一子節點，所以無序有序都一樣，3!=6種填法。而兩層節構下，樹根有兩子節點，有序無序就有差，有序有3!種填法。無序只有誰當樹根的差別，3種。所以綜合，有序樹有3!+3!棵，無序樹3!+3棵。free tree就當連通非循環圖，沒有誰當樹根的概念，三頂點用兩個邊變連通非循環，兩點degree是1，一點degree是2，就看degree是2的頂點要擺誰，3種放法。

謝謝兩位高手解惑