本篇主要講樹最基本的知識(shí)潭辈。
預(yù)備知識(shí)
一棵樹由稱做根root的節(jié)點(diǎn)r以及0個(gè)或者多個(gè)非空的(子)樹T1线罕，T1，...般哼，Tk組成吴汪，這些子樹中每一個(gè)棵的根都被來自根r的一條有向的邊edge鏈接。
-
兒子蒸眠、父親：
每一棵子樹的根節(jié)點(diǎn)叫做根r的兒子child漾橙，而r是每一棵子樹根的父親parent。例如A是E的父親楞卡，E是A的兒子霜运。 -
樹葉：
每一個(gè)子樹也可以有自己的兒子，而沒有兒子的子樹叫做樹葉leaf臀晃。例如B觉渴、C、P -
兄弟徽惋、祖父案淋、孫子
具有相同父親的節(jié)點(diǎn)為兄弟，類似的還有孫子和祖父险绘。例如D踢京、E為兄弟，A是J的祖父宦棺、J是A的孫子瓣距。 -
深度、高
從根到該節(jié)點(diǎn)唯一路徑的長(zhǎng)代咸。比如根的深度為0蹈丸。
從該節(jié)點(diǎn)到一片樹葉的最長(zhǎng)路徑的長(zhǎng)。比如所有的樹葉高都是0，一棵樹的高等于它根的高逻杖。
例如：E的深度為1奋岁，而高為2。F的深度是1荸百，而高也是1闻伶。
image.png
樹的實(shí)現(xiàn)
由于每個(gè)節(jié)點(diǎn)兒子數(shù)可以變化很大，并且事先不知道够话，因此在數(shù)據(jù)結(jié)構(gòu)中建立到各個(gè)兒子節(jié)點(diǎn)直接的鏈接是不可行的蓝翰，因?yàn)檫@樣會(huì)浪費(fèi)太多的空間。（這是書上的說法女嘲，我覺得估一個(gè)大概的數(shù)量畜份，直接把兒子數(shù)組的寬度寫死也是可以的）
這里的解法是：將每個(gè)節(jié)點(diǎn)的所有兒子都放在樹節(jié)點(diǎn)的鏈表中。
一種典型的聲明：
typedef struct TreeNode * PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode FirstClild;
PtrToNode NextSibling;
}
在下圖的表示方式中澡为，向下的紫色箭頭是指向FirstChild（第一個(gè)兒子）的指針漂坏。從左到右的箭頭是指向NextSibling（下一個(gè)兄弟）的指針。這里并沒有畫空指針媒至。
image.png
樹的遍歷及應(yīng)用
最流行的用法之一就是操作系統(tǒng)中的目錄結(jié)構(gòu)顶别。如下圖，有*號(hào)的表示一個(gè)目錄拒啰。
image.png
假設(shè)我們想要列出目錄中所有文件的名字驯绎。我們的輸出格式將是：深度
di 的文件的名字將被 di 次跳格(tab)縮進(jìn)后打印出來。
算法如下：
static void ListDir( DirectoryOrFile D, int Depth )
{
if( D is a legitimate entry) //合法入口
{
PrintName(D, Depth);
if( D is a directory )
for each child, C, of D
ListDir( C, Depth + 1 );
}
}
void ListDirectory( DirectoryOfFile D )
{
ListDir( D, 0 );
}
算法的核心為遞歸過程ListDir谋旦。為了顯示根時(shí)不進(jìn)行縮進(jìn)剩失，該例程需要從目錄名和深度0開始。
image.png
