題目描述
內容
本題是關於有根樹(rooted tree)。在一棵 n 個節點的有根樹中,每個節點都是以 1~n 的不同數字來編號,描述一棵有根樹必須定義節點與節點之間的親子關係。
一棵有根樹恰有一個節點沒有父節點(parent),此節點被稱為根節點(root),除了根節點以外的每一個節點都恰有一個父節點,而每個節點被稱為是它父節點的子節點(child),有些節點沒有子節點,這些節點稱為葉節點(leaf)。在當有根樹只有一個節點時,這個節點既是根節點同時也是葉節點。
在圖形表示上,我們將父節點畫在子節點之上,中間畫一條邊(edge)連結。例如,圖一中表示的是一棵 $9$ 個節點的有根樹,其中,節點 $1$ 為節點 $6$ 的父節點,而節點 $6$ 為節點 $1$ 的子節點;又$5、3、8$都是 $2$ 的子節點。節點 $4$ 沒有父親點,所以節點 $4$ 是根節點;而$6、9、3$與 $8$ 都是葉節點。
ShowImage