樹是一類重要的非線性資料結構，是以分支關係定義的層次結構
§6.1樹的定義
定義定義：樹(tree)是n(n>0)個結點的有限集t，其中：
有且僅有乙個特定的結點，稱為樹的根(root)
當n>1時，其餘結點可分為m(m>0)個互不相交的有限集t1,t2,……tm，其中每乙個集合本身又是一棵樹，稱為根的子樹(subtree)
特點：樹中最多只有乙個根結點
樹中各子樹是互不相交的集合
基本術語
結點(node)——表示樹中的元素，包括資料項及若干指向其子樹的分支結點的度(degree)——結點擁有的子樹數葉子(leaf)——度為0的結點
孩子(child)——結點子樹的根稱為該結點的孩子雙親(parents)——孩子結點的上層結點叫該結點的~兄弟(sibling)——同一雙親的孩子樹的度——一棵樹中最大的結點度數
結點的層次(level)——從根結點算起，根為第一層，它的孩子為第二層……
深度(depth)——樹中結點的最大層次數
森林(forest)——m(m0)棵互不相交的樹的集合
§6.2二叉樹
6.2.1定義
定義：二叉樹是n(n0)個結點的有限集，它或為空樹(n=0)，或由乙個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成特點
每個結點至多有二棵子樹(即不存在度大於2的結點)
二叉樹的子樹有左、右之分，且其次序不能任
意顛倒6.2.2二叉樹性質
性質1：在二叉樹的第i層上至多有2i-1個結點（i>=1）
性質2：深度為k的二叉樹至多有2k-1個結點(k1)性質3：對任何一棵二叉樹t，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1
兩種特殊形式的二叉樹
滿二叉樹
定義：深度為k,頂點個數為2-1的二叉樹叫滿二叉樹
k完全二叉樹
定義：深度為k，有n個結點的二叉樹當且僅當其每乙個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹性質4:具有n個結點的完全二叉樹的深度為log2n+1
x表示不大於x的最大整數x表示不小於x的最小整數
性質5：如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點
i(1in)，有：
(1)如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2(2)如果2i>n，則結點i無左孩子；如果2in，則其左孩子是2i
(3)如果2i+1>n，則結點i無右孩子；如果2i+1n，則其右孩子是2i+1
二叉樹的鏈式儲存表示二叉鍊錶
typedefstructnodetreenode,*treelink;
三叉鍊錶
typedefstructnodetreenode3;
使用性質5建立二叉樹#define max 20 ;treelinkp[max+1] ;treelink creattree(void)
printf (「input ich :」);scanf(「%d,%d」&i,&ch);}//endwhilereturn t ;}
6.3.1遍歷二叉樹一.先根遍歷1.遞迴演算法輸入：二叉樹
輸出：先根遍歷序列
1、if(二叉樹非空)1.1.訪問根結點
1.2.先根遍歷左子樹1.3.先根遍歷右子樹演算法的類c語言描述
viod preorder(treelink t)}
2、非遞迴演算法輸入：二叉樹t
輸出：先根遍歷序列1.初始化棧指向根結點
3. while（棧不空或p不是空指標）不是空指標）
3.1.1.輸出p所指結點資料3.1.2. p進棧
3.1.3. p指向p所指結點的左孩子
棧頂元素出棧
指向p所指結點的右孩子演算法的類c語言描述
voidpreorder2(treelink t)
else
}}時間複雜度o(n)二、中根遍歷1.遞迴演算法：輸入：二叉樹
輸出：中根遍歷序列
1、if(二叉樹非空)
1.1.中根遍歷左子樹1.2.訪問根結點
1.3.中根遍歷右子樹演算法的類c描述
viodmidorder(treelinkt)}
2、非遞迴法輸入：二叉樹t
輸出：中根遍歷序列1.初始化棧指向根結點
3. while（棧不空或p不是空指標）不是空指標）
3.1.1. p進棧
3.1.2. p指向p所指結點的左孩子
棧頂元素出棧3.2.2.輸出p所指結點資料
指向p所指結點的右孩子演算法的類c描述
voidmidorder2(treelink t)}
時間複雜度o(n)三、後根遍歷1.遞迴演算法：輸入：二叉樹
輸出：後根遍歷序列1、if(二叉樹非空)
1.1.後根遍歷左子樹1.2.後根遍歷右子樹1.3.訪問根結點演算法的類c描述
viodlastorder(treelinkt)
}說明：二叉樹的遍歷是二叉樹其他操作的基礎，在對二叉樹遍歷過程中可以對二叉樹的結點進行各種操作：求葉子結點個數，求結點的孩子結點，求結點的雙親結點，求二叉樹結點個數，建立二叉樹等等。
例：使用先序遍歷建立二叉樹：輸入：要指向二叉樹根的指標t
輸出：建立的二叉樹（返回樹根指標t）1.輸入資料data
不是結束符)申請根結點
2.2.將資料data賦給根結點2.3.先根建立先根建立為空類c描述：
viod precreat(treelink &t)else
t=null;}
1.求一棵二叉樹葉子結點的個數輸入：二叉樹t
輸出：葉子結點個數
1.初始化棧s，初始統計變數count＝指向根結點
3. while（棧不空或p不是空指標）不是空指標）
3.1.1.判斷p所指結點是否是葉子，是則count＋＋3.1.2. p進棧
3.1.3. p指向p所指結點的右孩子
棧頂元素出棧
指向p所指結點的左孩子
4.輸出count
2.求一棵二叉樹的深度輸入：二叉樹t
輸出：二叉樹的深度
1. if（t為空）2.返回樹深為
3.1求左子樹深度ld3.2.右子樹深度rd
3.2.返回樹深為max（ld，rd）＋1intdeep(treelinkt)
第六章樹和二叉樹
一 選擇題 1 已知一算術表示式的中綴形式為 a b c d e，字尾形式為abc de 其字首形式為 a a b c de b.a b cd e c abc ded.a bc de 北京航空航天大學 1999 一 3 2分 2 算術表示式a b c d e 轉為字尾表示式後為 中山大學 1999 ...
資料結構考研習題第六章樹和二叉樹
第六章樹和二叉樹 一 選擇題 1 已知一算術表示式的中綴形式為 a b c d e，字尾形式為abc de 其字首形式為 a a b c de b.a b cd e c abc ded.a bc de 北京航空航天大學 1999 一 3 2分 2 算術表示式a b c d e 轉為字尾表示式後為 中...
樹和二叉樹習題及答案
一 填空題 1.不相交的樹的聚集稱之為森林 2.從概念上講，樹與二叉樹是兩種不同的資料結構，將樹轉化為二叉樹的基本目的是 樹可採用孩子 兄弟鍊錶 二叉鍊錶 做儲存結構，目的是利用二叉樹的已有演算法解決樹的有關問題。3.深度為k的完全二叉樹至少有2 k 1個結點。至多有2 k 1個結點，若按自上而下，...