參考《數(shù)據(jù)結(jié)構(gòu)與算法分析-c語言描述》一書。

1、樹的基本知識

根：沒有父親的節(jié)點。
樹葉：沒有兒子的節(jié)點叫做樹葉，或者葉子結(jié)點。
兄弟：具有相同父親的節(jié)點成為兄弟節(jié)點。
路徑：從節(jié)點A到節(jié)點B的一個序列，該序列上任意相鄰兩個點是父子關系。
路徑的長：路徑上邊的條數(shù)。
深度：對每一個節(jié)點A，A的深度是從根到A的唯一路徑的長。
高度：一個樹的高度是樹到葉子結(jié)點最大的路徑長度。

2、樹的實現(xiàn)

實現(xiàn)樹的一種方法可以是在每一個節(jié)點除數(shù)據(jù)外還有一些指針，使得該節(jié)點的每一個兒子都有一個指針指向它。然后，由于每個節(jié)點的兒子數(shù)可以變化并且事先不知道，因此在數(shù)據(jù)結(jié)構(gòu)中建立到各兒子節(jié)點直接的鏈接是不可行的，因為這樣會產(chǎn)生太多的浪費空間。實際上解法很簡單：將每個節(jié)點的所有兒子都放在樹節(jié)點的鏈表中：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode * PtrToNode;

struct TreeNode
{
    int Element;
    PtrToNode FirstChild;
    PtrToNode NextSibling;
};

樹

這種表示方法想要得到如上圖所示A節(jié)點的所有子節(jié)點，只需要通過FirstChild找到B節(jié)點，根據(jù)B節(jié)點的NextSibling找到B所有的兄弟節(jié)點即可。

如果你喜歡我寫的文章，可以幫忙給小編點個贊或者加個關注，我一定會互粉的！
如果大家對數(shù)據(jù)結(jié)構(gòu)感興趣，歡迎跟小編進行交流，小編微信為sxw2251，加我要寫好備注喲?。?/p>

我的微信