邏輯非線性結(jié)構(gòu)

數(shù)據(jù)和數(shù)據(jù)之間是1：m

若某個節(jié)點有后繼,則后繼節(jié)點可以是多個

若某個節(jié)點有前驅(qū),則前驅(qū)節(jié)點只能是一個

可以把節(jié)點分成前驅(qū)節(jié)點和后繼節(jié)點

節(jié)點的度：若A節(jié)點有m個子節(jié)點,則節(jié)點A的度是m

樹的度·：樹中節(jié)點最大的度

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

樹的遍歷：對樹中所有節(jié)點,無遺漏,無重復(fù)的訪問一遍

遍歷的方法：

深度優(yōu)先遍歷：優(yōu)先訪問某一個“路徑”，直到葉子節(jié)點

根節(jié)點入棧;

while(棧非空){

node = pop(堆棧);

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

將node所有子節(jié)點入棧

}

廣度優(yōu)先遍歷：優(yōu)先訪問同層的所有節(jié)點

根節(jié)點入隊

while(隊非空){

node = out(隊列)；

Access(node);

將node所有子節(jié)點入隊

]

樹的表示法：

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);

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

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

將每一個節(jié)點的數(shù)據(jù)和其父節(jié)點的下標(biāo)放在一起

二叉數(shù)：

二叉樹的子節(jié)點分左右

滿二叉樹：高度為h的節(jié)點，節(jié)點總數(shù)為2^h-1

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

完全二叉樹

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

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

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

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

n總 = n0 + n1 +n2

n0 = n2 + 1

n總 = n1+2n0-1

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

no = n總/2