樹(shù)
在n個(gè)結(jié)點(diǎn)的樹(shù)中有n-1條邊。
樹(shù)中一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的度，樹(shù)中結(jié)點(diǎn)的最大度數(shù)稱為樹(shù)的度。
有序樹(shù)和無(wú)序樹(shù)（左右子樹(shù)是否有順序）
路徑只能從上到下，同一雙親結(jié)點(diǎn)的兩個(gè)孩子結(jié)點(diǎn)之間不存在路徑。
樹(shù)的性質(zhì)
1.結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1
2.度為m的樹(shù)中第i層上至多有m^(i-1)個(gè)結(jié)點(diǎn)
3.高度h的m叉樹(shù)至多有(m^h-1)/(m-1)個(gè)結(jié)點(diǎn)
4.具有n個(gè)結(jié)點(diǎn)的m叉樹(shù)的最小高度為：向上取整(log(m)(n(m-1)+1))
二叉樹(shù)
滿二叉樹(shù)
高度為h的，含有2^h-1個(gè)結(jié)點(diǎn)
若從1開(kāi)始，自上而下，自左向右對(duì)結(jié)點(diǎn)編號(hào)，i結(jié)點(diǎn)的父節(jié)點(diǎn)為i/2向下取整，左孩子2i，右孩子2i+1
完全二叉樹(shù)
每個(gè)結(jié)點(diǎn)的編號(hào)都與與其同高度的滿二叉樹(shù)一致
1.若i<=n/2向下取整，則i為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)
2.葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)。對(duì)于最大層次中的葉子結(jié)點(diǎn)，都依次排列在該層的最左邊
3.若有度為1的結(jié)點(diǎn)，則只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子
4.按層序編號(hào)后，一旦出現(xiàn)某編號(hào)為i的結(jié)點(diǎn)為葉子結(jié)點(diǎn)或只有左孩子，則編號(hào)大于i的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)
5.若n為奇數(shù)則每個(gè)分支結(jié)點(diǎn)都既有左節(jié)點(diǎn)又有右節(jié)點(diǎn)
6.i所在的層次為：向下取整（log(2)i）+1
7.具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為：向上取整（log(2)(n+1))或向下取整（log(2)n)+1
二叉排序樹(shù)
左子樹(shù)上的所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字，右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字。左子樹(shù)和右子樹(shù)又各是一顆二叉排序樹(shù)。
平衡二叉樹(shù)
任一結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度之差不超過(guò)1
二叉樹(shù)的性質(zhì)
1.度為0，1，2的結(jié)點(diǎn)個(gè)數(shù)分別為n0，n1，n2
結(jié)點(diǎn)數(shù)（n0+n1+n2）-1=分支數(shù)=n1+2*n2
-》n0=n2+1（葉節(jié)點(diǎn)數(shù)）
2.非空二叉樹(shù)第k層上至多有2^(k-1)個(gè)結(jié)點(diǎn)
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
完全二叉樹(shù)和滿二叉樹(shù)比較適合順序存儲(chǔ)，通過(guò)序號(hào)來(lái)反映父子關(guān)系
二叉樹(shù)一般采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中，含有n+1個(gè)空鏈域。
二叉樹(shù)的遍歷
按照根結(jié)點(diǎn)被訪問(wèn)的時(shí)機(jī)，分為先序NLR，中序LNR，后序LRN
遞歸
void PreOrder(BiTree T)
{
if(T!=NULL){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
每個(gè)結(jié)點(diǎn)都訪問(wèn)一次僅訪問(wèn)一次所以時(shí)間復(fù)雜度為O(n)
遞歸棧的深度恰好為樹(shù)的深度
非遞歸
void InOrder2(BiTree T)
{
InitStack(S); BiTree p=T;
while(p||!IsEmpty(S))
{
if(p){
Push(S,p);
p=p->lchild;
}
else{
Pop(S,p); visit(p);
p=p->rchild;
}
}
}
p首先指向根節(jié)點(diǎn)，將p入棧，并使p指向其左節(jié)點(diǎn)，若p為null（沒(méi)有左節(jié)點(diǎn)），則出棧并訪問(wèn)，再將p指向其右節(jié)點(diǎn)。
后序的非遞歸
因?yàn)樵谧?，右子?shù)都處理完畢之前不可將根從棧中移除，則需要在入棧時(shí)添加額外信息rvisited來(lái)標(biāo)識(shí)，是從左子樹(shù)回來(lái)的還是從右樹(shù)回來(lái)的。
typedef struct{
BTNode *p;
int rvisited; //為1的時(shí)候代表p所指向的結(jié)點(diǎn)的右節(jié)點(diǎn)已被訪問(wèn)過(guò)
}SNode; //棧中的結(jié)點(diǎn)定義
typedef struct{
SNode Elem[maxsize]
int top;
}SqStack; //棧結(jié)構(gòu)體
void PostOrder2(BiTree T)
{
SNode sn;
BTNode *pt=T
InitStack(S);
while(T){ //向左走到盡頭，并把路徑上的元素全部入棧
Push(pt,0);
pt=pt->lchild;
}
while(!S.IsEmpty()){
sn=S.getTop();
//棧頂結(jié)點(diǎn)的左子樹(shù)一定是已經(jīng)遍歷完了
//因?yàn)樽笞訕?shù)上的結(jié)點(diǎn)一定在它的上面
if(sn.p->rchild==NULL||sn.rvisited){
//若棧頂元素?zé)orchild或rchild已被訪問(wèn)過(guò)，則出棧并訪問(wèn)它
Pop(S, pt);
visit(pt);
}
else{
//如果有rchild且未被訪問(wèn)，則去訪問(wèn)它的rchild
sn.rvisited=1;
pt=sn.p->rchild;
while(pt!=NULL){
Push(pt, 0);
pt=pt->lchild;
}
}
}
}
層次遍歷
void LevelOrder(BiTree T)
{
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!IsEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
由遍歷序列構(gòu)造二叉樹(shù)
由二叉樹(shù)的先序序列和中序序列可以唯一確定一棵二叉樹(shù)
由二叉樹(shù)的后序序列和中序序列可以唯一確定一棵二叉樹(shù)
由二叉樹(shù)的層序序列和中序序列可以唯一確定一棵二叉樹(shù)
由二叉樹(shù)的先序序列和后序序列不可以唯一確定一棵二叉樹(shù)
二叉樹(shù)遍歷的應(yīng)用
求二叉樹(shù)的高度
遞歸 H=max(Hl+Hr)+1
int PostOrderGetHeight(BinTree BT)
{
int Hl,Hr,maxH;
if(BT){
Hl=PostOrderGetHeight(BT->left);
Hr=PostOrderGetHeight(BT->right);
maxH=(Hl>Hr)?Hl:Hr;
return (maxH+1);
}
else return 0;
}
二元運(yùn)算表達(dá)式及其遍歷
用后綴表達(dá)式構(gòu)造一棵樹(shù)
思路類似用后綴表達(dá)式求值
依次讀取，若遇到操作數(shù)，則建立一個(gè)單節(jié)點(diǎn)樹(shù)并入棧，若遇到操作符，建立一個(gè)單節(jié)點(diǎn)，則從棧中彈出棧頂?shù)膬煽脴?shù)T1，T2，將該節(jié)點(diǎn)作為根，T2，T1作為左右子樹(shù)，再將這個(gè)樹(shù)入棧
樹(shù)和森林
**樹(shù)的存儲(chǔ)結(jié)構(gòu)
1.雙親表示法
采用一組連續(xù)空間來(lái)存儲(chǔ)每個(gè)結(jié)點(diǎn)，在每個(gè)結(jié)點(diǎn)中增設(shè)一個(gè)偽指針，指示雙親結(jié)點(diǎn)在數(shù)組中的位置
#define MAX_TREE_SIZE 100
typedef struct{
ElemType data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n;
}PTree;
可快速找到父節(jié)點(diǎn)但求子節(jié)點(diǎn)時(shí)需遍歷整個(gè)結(jié)構(gòu)
2.孩子表示法
將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)都用單鏈表鏈接起來(lái)形成一個(gè)線性結(jié)構(gòu)
3.孩子兄弟表示法
又稱二叉樹(shù)表示法
每個(gè)結(jié)點(diǎn)包括三部分：結(jié)點(diǎn)值，指向結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)的指針，指向結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)的指針
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
樹(shù)，森林與二叉樹(shù)的轉(zhuǎn)換
樹(shù)和森林的遍歷
樹(shù)的遍歷
先根遍歷：若樹(shù)非空，則先訪問(wèn)根結(jié)點(diǎn)，再按從左到右的順序遍歷根結(jié)點(diǎn)的每棵子樹(shù)，其訪問(wèn)順序與這棵樹(shù)相應(yīng)二叉樹(shù)的先序遍歷順序相同。
后根遍歷：若樹(shù)非空，則按從左到右的順序遍歷根結(jié)點(diǎn)的每棵子樹(shù)，之后再訪問(wèn)根結(jié)點(diǎn)。其訪問(wèn)順序與這棵樹(shù)對(duì)應(yīng)的二叉樹(shù)的中序遍歷相同。
森林的遍歷
樹(shù)的應(yīng)用——并查集
有一些元素，各自為一個(gè)集合，若元素A與元素B有關(guān)系，則把它們并到同一集合，若A和C也有關(guān)系，就把C集合與之前AB合并后的集合合并。最后同一集合中的任意兩個(gè)元素都是有關(guān)系可連通的。
并查集是一種集合表示，支持以下三種操作
1.Union(S, Root1, Root2)
把集合S中的子集合Root2并入Root1中，Root1與Root2互不相交
2.Find(S, x)
查找集合S中單元素x所在的子集合
3.Initial(S)
將集合S中的每個(gè)元素初始化為只有一個(gè)單元素的子集合
通常用雙親表示法作為并查集額存儲(chǔ)結(jié)構(gòu)，每個(gè)子集以一棵樹(shù)表示。
初始化時(shí)每個(gè)元素自成一個(gè)單元素子集合
用數(shù)組存儲(chǔ)
typedef struct{
ElementType Data;
int Parent;
}SetType;
查找某元素所在的集合
int Find(SetType S[], ElementType X)
{
int i;
for(i=0;i<MaxSize&&S[i].Data!=X;++i);
if(i>=MaxSize) return -1; //cannot find
for(;S[i].parent>=0;i=S[i].parent);
return i;
}
集合的并運(yùn)算
void Union(SetType S[], ElementType X1, ElementType X2)
{
int Root1,Root2;
Root1=Find(S, X1); Root2=Find(S, X2);
if(Root1!=Root2)
S[Root2].parent=Root1;
}
數(shù)越深Find就越耗時(shí)，所以合并時(shí)盡量讓小的樹(shù)的parent指向大的樹(shù)的根，改進(jìn)方法是根節(jié)點(diǎn)的parent不再為-1而是數(shù)中元素個(gè)數(shù)的負(fù)值
