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

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

若某個(gè)節(jié)點(diǎn)有后繼,則后繼節(jié)點(diǎn)可以是多個(gè)

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

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

節(jié)點(diǎn)的度：若A節(jié)點(diǎn)有m個(gè)子節(jié)點(diǎn),則節(jié)點(diǎn)A的度是m

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

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

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

遍歷的方法：

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

根節(jié)點(diǎn)入棧;

while(棧非空){

node = pop(堆棧);

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

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

}

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

根節(jié)點(diǎn)入隊(duì)

while(隊(duì)非空){

node = out(隊(duì)列)；

Access(node);

將node所有子節(jié)點(diǎn)入隊(duì)

]

樹的表示法：

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

使用上述方式申請(qǐng)一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目，那么這個(gè)子節(jié)點(diǎn)的數(shù)目就被固定

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

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

二叉數(shù)：

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

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

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

完全二叉樹

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

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

3.任意一個(gè)二叉樹：n0 = n2 + 1

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

n總 = n0 + n1 +n2

n0 = n2 + 1

n總 = n1+2n0-1

因?yàn)閚總是偶數(shù),則其葉子數(shù)是奇數(shù)個(gè),所以n1= 1

no = n總/2