[有向樹] 一個弱連通有向圖，若去掉方向後得到一棵樹，則稱此有向圖爲一棵有向樹，記爲T。

[外向樹] 若一個有向樹T，有且只有一個頂點入度爲0，其餘頂點入度都爲1，則稱T爲外向樹。T中入度爲0的節點被稱爲T的根節點，出度爲0的節點被稱爲T的葉節點。每個節點的有向邊指向的節點被稱爲該節點的子節點。

[內向樹] 若一個有向樹T，有且只有一個頂點出度爲0，其餘頂點出度都爲1，則稱T爲內向樹。T中出度爲0的節點被稱爲T的根節點，入度爲0的節點被稱爲T的葉節點。每個節點的有向邊的反向邊指向的節點被稱爲該節點的子節點。

外向樹和內向樹都是有根樹。

圖1	圖2

如上，圖1爲一棵外向樹，圖2爲一棵內向樹。

[樹的括號序列最小表示法]

定義S[t]表示以t爲根的子樹的括號序列

S[t]=

{

'(',')' (如果t爲葉節點)

'(',S[c1],S[c2],...,S[ck],')' (c1,c2,...,ck爲t的k個子節點，S[c1],S[c2],...,S[ck]要按照字典序排列)

}

爲了保證同構的樹的括號序列表示具有唯一性，我們必須規定子樹點的順序。按照子樹的括號序列的字典序就是一種不錯的方法。

例如上述圖2，它的括號序列最小表示就是((()()())())。

[有根樹的同構]

對於一個有根樹，我們可以通過比較他們的括號序列的最小表示，如果他們的括號序列最小表示完全相等，那麼他們同構。

BYVoid 原創講解，轉載請註明。