有向樹與樹的括號序列最小表示法
本文正體字版由OpenCC轉換
[有向樹] 一個弱連通有向圖，若去掉方向後得到一棵樹，則稱此有向圖爲一棵有向樹，記爲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 原創講解，轉載請註明。
上次修改時間 2017-05-26