數(shù)據(jù)結(jié)構(gòu)與算法課件7-2二叉樹的建立

7.2.3.二叉樹的性質(zhì)性質(zhì)1在一棵非空二叉樹的第i層上至多有2i個結(jié)點（i≥0）。性質(zhì)2深度為k的二叉樹至多有2k+1-1個結(jié)點。

說明：深度k=-1，表示沒有一個結(jié)點；深度k=0，表示只有一個根結(jié)點。性質(zhì)3對于一棵非空的二叉樹，如果葉結(jié)點個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有n0=n2+1。性質(zhì)4具有n個結(jié)點的完全二叉樹的深度k為大于或等于lb(n+1)-1的最小整數(shù)。

對于一棵有n個結(jié)點的完全二叉樹，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點從0開始順序編號,則對于序號為i的結(jié)點(0≤i<n),有：

(1)如果i=1，則結(jié)點i是根結(jié)點，無雙親。(2)如果2i＜n，其左孩子是結(jié)點2i；如果2i≥n，則結(jié)點i無左孩子。

(3)如果2i+1＜n，其右孩子是結(jié)點2i＋1；如果2i＋1≥n，則結(jié)點i無右孩子。性質(zhì)5BACEDFGHIJKLMNOABCDONMLKJIHGFE12043576118109121314

對于一般的非完全二叉樹顯然不能直接使用二叉樹的順序存儲結(jié)構(gòu)?？梢允紫仍诜峭耆鏄渲性鎏硪恍┎⒉淮嬖诘目战Y(jié)點使之變成完全二叉樹的形態(tài)，然后再用順序存儲結(jié)構(gòu)存儲。BACEDFGHIJABCDJIHGFE1204357689BACDEGFBACDEGF(a)一般二叉樹(b)完全二叉樹形態(tài)(c)在數(shù)組中的存儲形式ABC∧G∧∧F∧∧∧ED1204357611810912數(shù)組下標1.二叉樹遍歷的基本方法

從二叉樹的定義知，一棵二叉樹由三部分組成：根結(jié)點、左子樹和右子樹。若規(guī)定D,L,R分別代表“訪問根結(jié)點”、“遍歷根結(jié)點的左子樹”和“遍歷根結(jié)點的右子樹”。根據(jù)遍歷算法對訪問根結(jié)點處理的位置，稱下面三種遍歷算法分別為：

前序遍歷（DLR）中序遍歷（LDR）后序遍歷（LRD）7.3.2二叉樹的遍歷

前序遍歷（DLR）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：（1）訪問根結(jié)點；（2）前序遍歷根結(jié)點的左子樹；（3）前序遍歷根結(jié)點的右子樹。對于如圖所示的二叉樹，前序遍歷訪問結(jié)點的次序為：ABDFCEG中序遍歷（LDR）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：（1）中序遍歷根結(jié)點的左子樹；（2）訪問根結(jié)點；（3）中序遍歷根結(jié)點的右子樹。對于圖7-7（b）所示的二叉樹，中序遍歷訪問結(jié)點的次序為：BFDAEGC后序遍歷（LRD）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：（1）后序遍歷根結(jié)點的左子樹；（2）后序遍歷根結(jié)點的右子樹；（3）訪問根結(jié)點。對于如圖所示的二叉樹，后序遍歷訪問結(jié)點的次序為：FDBGECA//以先根遍歷創(chuàng)建二叉樹,AB#D##C##voidCreat(BiTree*bt){Elemtypech; printf("請輸入字符AB#D##C##:"); scanf("%c",&ch); getchar(); if(ch=='#') *bt=NULL;

else {*bt=(BiTree)malloc(sizeof(btNode));//分配根節(jié)點

if(!*bt) {printf("分配節(jié)點失敗\n"