中國(guó)著名特級(jí)教師教學(xué)思想錄26

《中國(guó)著名特級(jí)教師教學(xué)思想錄26》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、樹和圖西安交通大學(xué)計(jì)教中心ctec.xjtu.edu.cn樹的遞歸定義:樹是由n個(gè)具有相同特性的數(shù)據(jù)元素組成的集合。若n=0，則稱其為空樹。一棵非空樹T必須滿足：1）其中有一個(gè)特定的元素稱為T的根root。2）除根以外的集合可被劃分為m個(gè)不相交的子集T1，T2，…，Tm，其中每個(gè)子集都是樹。它們稱為根root的子樹。GACFDEB樹的一般形式與樹相關(guān)的術(shù)語(yǔ)?結(jié)點(diǎn)：在樹結(jié)構(gòu)中一般把數(shù)據(jù)元素及其若干指向子樹的分支稱為結(jié)點(diǎn)。?結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的非空子樹的個(gè)數(shù)。?樹的度：樹中所有結(jié)點(diǎn)的度的最大值。?葉子結(jié)點(diǎn)：沒(méi)有非空子樹的結(jié)點(diǎn)。

2、?分支結(jié)點(diǎn)：至少有一個(gè)非空子樹的結(jié)點(diǎn)。?孩子結(jié)點(diǎn)和父結(jié)點(diǎn)：某結(jié)點(diǎn)所有子樹的根結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，同時(shí)該結(jié)點(diǎn)也稱為其孩子結(jié)點(diǎn)的父結(jié)點(diǎn)。?兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。?結(jié)點(diǎn)的層次：根結(jié)點(diǎn)的層次為1,其子結(jié)點(diǎn)的層次為2。依次類推，子結(jié)點(diǎn)的層次總比父結(jié)點(diǎn)多一層。?樹的深度：樹中結(jié)點(diǎn)所在的最大層次。?有序樹和無(wú)序樹：將樹中各結(jié)點(diǎn)的子樹看成自左向右有序的，則稱該樹為有序樹。否則稱為無(wú)序樹。?森林：由零棵或有限棵互不相交的樹組成的集合。二叉樹的定義二叉樹可以是空樹，當(dāng)二叉樹非空時(shí)，其中有一個(gè)根元素，余下的元素組成兩

3、個(gè)互不相交二叉樹，分別稱為根的左子樹和右子樹。二叉樹是有序樹，也就是說(shuō)任意結(jié)點(diǎn)的左、右子樹不可交換。而一般樹的子樹間是無(wú)序的。特殊形式的二叉樹滿二叉樹：當(dāng)二叉樹每個(gè)分支結(jié)點(diǎn)的度都是2，且所有葉子結(jié)點(diǎn)都在同一層上，則稱其為滿二叉樹。完全二叉樹：從滿二叉樹葉子所在的層次中，自右向左連續(xù)刪除若干葉子所得到的二叉樹被稱為完全二叉樹。滿二叉樹可看作是完全二叉樹的一個(gè)特例。AFC滿二叉樹GDBEAC完全二叉樹DBE二叉樹有下列重要性質(zhì)：（1）在二叉樹的第k層上至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)證明：當(dāng)k=1時(shí)，命題顯然成立。假定k=n-1時(shí)

4、命題成立，則第n層（k=n）的結(jié)點(diǎn)數(shù)最多是第n-1層的2倍，所以第n層最多有2*2n-2=2n-1個(gè)結(jié)點(diǎn)。命題成立。（2）深度為h的二叉樹上至多含2h-1個(gè)結(jié)點(diǎn)(h≥1)證明：根據(jù)性質(zhì)1容易知道深度為h的二叉樹最多有20+21+…+2h-1個(gè)結(jié)點(diǎn)，即最多有2h-1個(gè)結(jié)點(diǎn)。（3）包含n(n>0)個(gè)結(jié)點(diǎn)的二叉樹總的分支數(shù)為n-1證明：二叉樹中除了根結(jié)點(diǎn)之外每個(gè)元素有且只有一個(gè)父結(jié)點(diǎn)。在所有子結(jié)點(diǎn)與父結(jié)點(diǎn)間有且只有一個(gè)分支，即除根外每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)分支，因此二叉樹總的分支數(shù)為n-1。（4）任何一棵二叉樹，若含有n0個(gè)葉子結(jié)點(diǎn)、n2

5、個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式n0=n2+1證明：設(shè)二叉樹含有n1個(gè)度為1的結(jié)點(diǎn)，則二叉樹結(jié)點(diǎn)總數(shù)顯然為：n0+n1+n2（2-2）再看看樹的分支數(shù)，n2個(gè)度為2的結(jié)點(diǎn)必然有2n2個(gè)分支，n1個(gè)度為1的結(jié)點(diǎn)必然有n1個(gè)分支。又因?yàn)槌Y(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(jìn)入。因此二叉樹的分支數(shù)加1就是結(jié)點(diǎn)總數(shù)。即結(jié)點(diǎn)總數(shù)為：1+n1+2n2（2-3）由（2-2）（2-3）兩式可知：n0=n2+1（5）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2(n)]+1證明：假設(shè)二叉樹的深度為h，則必有2h-1-1

6、n，則該結(jié)點(diǎn)無(wú)左孩子。否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；③若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子。否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。證明通過(guò)對(duì)i進(jìn)行歸納即可得證。二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)點(diǎn)定義：structBinTreeN

7、ode{ElemTypedata;structBinTreeNode*leftChild,*rightChild;};這里leftChild和rightChild分別為某一結(jié)點(diǎn)指向其左孩子和右孩子的指針。對(duì)于葉子結(jié)點(diǎn)或一個(gè)新生成的結(jié)點(diǎn)而言，其左孩子和右孩子指針都應(yīng)為空值。二叉樹的鏈?zhǔn)酱鎯?chǔ)ABC∧∧D∧∧E∧∧利用這種結(jié)點(diǎn)形式存儲(chǔ)的樹一般稱為二叉鏈表。從根結(jié)點(diǎn)出發(fā)，可以訪問(wèn)二叉樹的任何結(jié)點(diǎn)。為了能夠訪問(wèn)二叉樹，必須保留指向根結(jié)點(diǎn)的指針。這和單鏈表必須保留頭指針的道理一樣。二叉樹的常用算法包括：獲取根結(jié)點(diǎn)指針、判斷樹是否為空、插

8、入或刪除結(jié)點(diǎn)、插入或刪除子樹、二叉樹遍歷等。二叉樹類可描述如下：classBinTree{public:BinTreeNode*root;//定義根結(jié)點(diǎn)指針BinTree(){root=NULL;}//構(gòu)造函數(shù)，定義空樹//判斷樹是否為空boolIsEmpty(){returnroot==