邏輯非線性結構

數據和數據之間是1：m

若某個節點有后繼,則后繼節點可以是多個

若某個節點有前驅,則前驅節點只能是一個

可以把節點分成前驅節點和后繼節點

節點的度：若A節點有m個子節點,則節點A的度是m

樹的度·：樹中節點最大的度

度為n,高度為h的樹中，最多有多少個節點？：1+n+n^2+n^3+....+n^(h-1)

樹的遍歷：對樹中所有節點,無遺漏,無重復的訪問一遍

遍歷的方法：

深度優先遍歷：優先訪問某一個“路徑”，直到葉子節點

根節點入棧;

while(棧非空){

node = pop(堆棧);

access(node); // 訪問node節點的值

將node所有子節點入棧

}

廣度優先遍歷：優先訪問同層的所有節點

根節點入隊

while(隊非空){

node = out(隊列)；

Access(node);

將node所有子節點入隊

]

樹的表示法：

typedef  ... USER_TYPE;

typedef struct TREE{

USER_TYPE value;

struct  TREE *child;

int childCount;

}TREE;

TREE *tree;

tree->child = (TREE *)malloc(sizeof(TREE) * tree->childCount);

使用上述方式申請一個節點的子節點數目，那么這個子節點的數目就被固定

另一種方法：將節點依次排上編號,從0開始

將每一個節點的數據和其父節點的下標放在一起

二叉數：

二叉樹的子節點分左右

滿二叉樹：高度為h的節點，節點總數為2^h-1

一顆二叉樹的節點總數為n，則二叉樹的高度是[log(2)n]+1

完全二叉樹

1.假設一個完全二叉樹的節點總數是n,且從上到下,從左到右一次編號。那么為 i 的節點如果有左節點,那么左節點的編號是2*i,右節點的個數是2*i+1

2.一個高度為h的二叉樹,其節點總數最少是2^(h-1)，最多是2^h-1個

3.任意一個二叉樹：n0 = n2 + 1

問題：一個節點總數是n的二叉樹，n為偶數，則葉子節點數是多少？

n總 = n0 + n1 +n2

n0 = n2 + 1

n總 = n1+2n0-1

因為n總是偶數,則其葉子數是奇數個,所以n1= 1

no = n總/2