|
Tree implementation (reminder)
|
|
撰/ahliu
前言Tree的定義為「a connected undirected graph with no simple circuits」，這個名詞由1857年英國數學家Authur Cayley開始使用，起初是用來解決列舉飽和碳氫化合物(即saturated hydrocarbon)異構體的問題，後來，基於這數學基礎，提供了自然的方法來模疑電話網絡及分佈式網絡系統，利用與Tree相關的算法來計算資訊流量，及制定資訊傳播方法等等。大部分可利用Tree來模疑的問題，其資料或資料存取過程都含有先後(或繼承)關係或被包含的(類別包含資料，而類別及資料分別為tree node及tree element)關係。 基本定理- An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.
首先，所有vertices都有1條或以上的edge連繫著，因此一定存在著某path連繫tree內某兩個vertices；若你想由tree裡的x點去y點，並且有兩條path能乎合由x點去y點的要求，那麼x和y之間的兩條path就形成了一個圈，因此違反了tree的定義，所以在tree中，由x去y的path是唯一的。 - A tree with n vertices has n - 1 edges.
我們隨便選一個vertex為root，由root到tree的其他點都是依靠其唯一的path，因此當我們嘗試由root逐步搜尋，每搜尋多個vertex，就需要行多一個新的edge，當我們搜尋了所有的vertex，即代表搜尋了所有的edge，由於我們除root外，共有n - 1個點，因此我們便會找到n - 1個新edge。 若我們定義了Tree內edge的流向，自然地便有一個流動的源頭，這個源頭稱為root，這Tree也被稱為rooted tree，只要我們任意取tree的其中一個vertex為root，便能定義所有edge的流向。若x點經一個edge流向y點，我們稱x為parent(父)，稱y為child(子)；若x點經由一個或多個edge流向y點，我們稱x為ancestor(祖先)，稱y為descendant(後代)，當然parent也是ancestor的一種，而child也是descendant的一種。若x和y的parent都是z，那麼x便是y的sibling(同胞)，當然y也稱作x的sibling。 - A full m-ary tree with i internal vertices contains n = mi + 1 vertices
所謂m-ary tree即是每個internal vertex(即是有child的vertex，反義為leaf)最多有m個child，而full m-ary tree即是每個internal vertex都肯定有m個child。既然每個internal vertex都有m個child，那麼i個internal vertex便有mi個child，連同root加起來便有mi + 1個vertices - A full m-ary tree with
(i) n vertices has i = (n - 1)/m internal vertices and l = [(m - 1)n + 1]/m leaves
(ii) i internal vertices has n = mi + 1 vertices and l = (m - 1)i + 1 leaves
(iii) l leaves has n = (ml - 1)/(m - 1) vertices and i = (l - 1)/(m - 1) internal vertices
(i)是剛才的公式中調換i作主體，純粹來自n = mi + 1的。因為n個vertex裡有i個是internal vertices，那麼即是有n - i個vertices是leaf，因此得出l = n - (n - 1)/m。
(ii)是將n = mi + 1代進[(m - 1)n + 1]/m後的結果。
(iii)是將(i)的公式主體調換。 - There are at most mh leaves in an m-ary tree of height h.
首先，tree level的定義為由root到該vertex所經過的edge總數，而tree height是所有vertices裡最大的tree level，即是最遠的vertex距離root有多少遠。
利用數學歸納法(mathematical induction)，首先，考慮一個height是1的tree，其root最多只有m個child，因此它最多只有m1 = m個leaves；假設所有height為k的tree，最多都只有mk，現在我們把root拋開，便生成最多m個height為(k - 1)的subtree，根據剛才的inductive hypothesis，它們的leaves總數最多為mk-1]；最後，我們把m個subtree的mk-1個leaves加起來，便有最多m.mk-1 = mk個leaves，證明了其inductive argument。
Tree的實踐我們要表達parent和child以及sibling互相的關係，可嘗試由edge改為：
現在，斜線代表parent vertex指向它的第一個child，橫線代表右邊的vertex和左邊的vertex為sibling關係。這種tree我們稱為ordered rooted tree，因為vertices是由左至右排序的。既然如此，一個vertex應該包含的資料包括： typedef struct _treenode {
int value;
struct _treenode *child;
struct _treenode *sibling;
} TREENODE;
然後你將會把tree有可能的運作都寫了出來，包括加入vertex，刪除vertex，列印tree等，以下數段程式碼以供參考： TREENODE* tree_add_child(TREENODE *node, int value) {
TREENODE *sibling;
if (node == NULL) { /* The tree is empty now */
node = (TREENODE*) malloc(sizeof(TREENODE));
node->value = value;
node->child = NULL:
node->sibling = NULL:
return node;
} else {
if (node->child == NULL) {
node->child = (TREENODE*) malloc(sizeof(TREENODE));
node->child->value = value;
node->child->child = NULL;
node->child->sibling = NULL;
return node->child;
} else {
sibling = node->child;
while (sibling->sibling != NULL)
sibling = sibling->sibling;
sibling->sibling = (TREENODE*) malloc(sizeof(TREENODE));
sibling->sibling->value = value;
sibling->sibling->child = NULL;
sibling->sibling->sibling = NULL;
return sibling->sibling;
}
}
}
void tree_delete_all(TREENODE *node) {
if (node != NULL) {
tree_delete(node->child);
tree_delete(node->sibling);
free(node);
}
}
void tree_traverse(TREENODE *node) {
if (node != NULL) {
printf("(%d", node->value);
if (node->child != NULL) {
tree_traverse(node->child);
}
printf(")");
}
if (node->sibling != NULL)
tree_traverse(node->sibling);
}
請注意，刪除個別vertex即是tree_traverse及tree_delete_all的混合，而tree_traverse的顯示格式為(vertex(subtree1)(subtree2)...(subtreen))。
相關文件：
- Tree conversion
發表日期：2004-09-01
|
|
|
隨 機 文 章 
