中國著名特級教師教學思想錄26

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

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

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

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

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

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

6、n，則該結(jié)點無左孩子。否則，編號為2i的結(jié)點為其左孩子結(jié)點；③若2i+1>n，則該結(jié)點無右孩子。否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。證明通過對i進行歸納即可得證。二叉樹的鏈式存儲結(jié)點定義：structBinTreeN

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

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