回顧：

????棧——先進先出FILO

????隊列——先進后出FIFO

樹形結構（邏輯結構）

struct?Node{//樹結點的定義

????EleType data;//樹結點的數(shù)據(jù)域

????Node *child[];//子結點指針集合

};

????對于子結點指針，有可能用數(shù)組實現(xiàn)，也可能用鏈表實現(xiàn)，樹還可以使用數(shù)組實現(xiàn)，只需記錄每個結點的父結點即可。

????樹的基礎術語：

????1、父結點、子結點、兄弟結點，祖先、子孫

????2、結點的度，樹的度

????????結點的度——幾個子結點

????????樹的度——結點的度的最大值

????3、葉子結點（終端結點）與分支結點（非終端結點）

????????????度為零? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 度不為零

????4、結點的深度，高度和層次

????5、路徑和路徑長度

森林——樹的集合

????例題1：度為4的樹，度為4的結點2個，度為3的結點2個，度為2的結點0個，度為1的結點5個，總共有幾個結點？

畫圖法——

解析法——度為4的結點2個（2*4=8），度為3的結點2個（3*2=6）....

????????????????????合計8+6+0+5+1（根結點） = 20個

例題2：度為5的樹，度為5的結點2個，度為4的結點3個，度為3的結點5個，度為2的結點10個，度為1的結點20個，求總結點數(shù)和葉子結點數(shù)。

????解析法：5*2+4*3+3*5+2*10+1*20+1=78個總結點數(shù)

????????????????78-2-3-5-10-20=38個葉子結點（度為零）

二叉樹——度為2、1、0，且嚴格區(qū)分左右

struct Node{//二叉樹的結點定義

????EleType data;//二叉樹結點的數(shù)據(jù)域

????Node *left_child, *right_child;//左子結點與右子結點指針

};

左子樹與右子樹常寫作left(lchild)和right(rchild),同理二叉樹也能使用數(shù)組來存儲。

二叉樹的基本術語：

????1、左孩子（左子樹），右孩子（右子樹）

????2、每層的結點個數(shù)

????每層最多有多少個結點

????????第一層：1個

????????第二層：2個

????????第三層：4個

????????第n層：2^(n-1)個

????????總共最多有2^n-1個

????3、滿二叉樹，完全二叉樹

????????高度為10的滿二叉樹有2^10-1=1023結點。

????????完全二叉樹可以刪掉最后一層最靠右的結點，滿二叉樹是特殊的完全二叉樹

????4、使用一維數(shù)組存儲二叉樹

例如：若樹根數(shù)組下標為1，某結點下標x，左結點下標2*x,右結點2*x+1

????5、廣義表

結點（左子樹（），右子樹（））

例題1：完全二叉樹第四層有四個葉子結點，總共有多少個結點？

????若總共有4層，則1+2+4+4=11個

????若總共有5層且父結點都有右子樹，則1+2+4+8+8=23個，否則為23-1=22個