樹(shù)與二叉樹(shù)復(fù)習(xí)進(jìn)程

1、樹(shù)（非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)樹(shù)（非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)(sh j ji u)）第一頁(yè)，共26頁(yè)。第二頁(yè)，共26頁(yè)。 A A C C G G T T2 2 B B E E L L K KT T1 1 F FD D H H I I T T3 3J J M M現(xiàn)實(shí)世界中，能用樹(shù)的結(jié)構(gòu)表示的例子：現(xiàn)實(shí)世界中，能用樹(shù)的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類(lèi)的家族學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類(lèi)的家族(jiz)(jiz)血緣血緣關(guān)系等。關(guān)系等。計(jì)算機(jī)軟件技術(shù)中，能用樹(shù)的結(jié)構(gòu)表示計(jì)算機(jī)軟件技術(shù)中，能用樹(shù)的結(jié)構(gòu)表示(biosh)(biosh)的例子：的例子：操作系統(tǒng)中的多級(jí)文件目錄結(jié)構(gòu)，高級(jí)語(yǔ)言中源程序的語(yǔ)法操作

2、系統(tǒng)中的多級(jí)文件目錄結(jié)構(gòu)，高級(jí)語(yǔ)言中源程序的語(yǔ)法結(jié)構(gòu)等。結(jié)構(gòu)等。第三頁(yè)，共26頁(yè)。有關(guān)樹(shù)的基本術(shù)語(yǔ)有關(guān)樹(shù)的基本術(shù)語(yǔ): :結(jié)點(diǎn)（結(jié)點(diǎn)（NodeNode）：樹(shù)中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)）：樹(shù)中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。的分支。結(jié)點(diǎn)的度（結(jié)點(diǎn)的度（DegreeDegree）：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。）：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層. .葉子（葉子（LeafLeaf）：度為零的結(jié)點(diǎn)，也稱(chēng)端結(jié)點(diǎn)。）：度為零的結(jié)點(diǎn)，也稱(chēng)端結(jié)點(diǎn)。孩子（孩子（ChildChild）：結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。）：結(jié)點(diǎn)子樹(shù)的根稱(chēng)為

3、該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。雙親（雙親（ParentParent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱(chēng)為這些結(jié)點(diǎn)的雙）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱(chēng)為這些結(jié)點(diǎn)的雙親。親。兄弟兄弟(xingd)(xingd)（SiblingSibling）：同一雙親的孩子。）：同一雙親的孩子。深度（深度（Depth)Depth)： 樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。森林（森林（ForestForest）：）：M M棵互不相交的樹(shù)的集合?？没ゲ幌嘟坏臉?shù)的集合。 A C G T2 B E L KT1 FD H I T3J M C G T2 B E L KT1 FD H I T3J M第四頁(yè)，共26頁(yè)。 樹(shù)的存儲(chǔ)結(jié)構(gòu)可以采用具有多個(gè)指

4、針域的多重鏈表，結(jié)點(diǎn)中指針域樹(shù)的存儲(chǔ)結(jié)構(gòu)可以采用具有多個(gè)指針域的多重鏈表，結(jié)點(diǎn)中指針域的個(gè)數(shù)應(yīng)由樹(shù)的度來(lái)決定的個(gè)數(shù)應(yīng)由樹(shù)的度來(lái)決定 但在實(shí)際應(yīng)用但在實(shí)際應(yīng)用(yngyng)(yngyng)中，這種存儲(chǔ)結(jié)構(gòu)并不方便，一般將樹(shù)轉(zhuǎn)中，這種存儲(chǔ)結(jié)構(gòu)并不方便，一般將樹(shù)轉(zhuǎn)化為二叉樹(shù)表示，進(jìn)行處理化為二叉樹(shù)表示，進(jìn)行處理 可以用樹(shù)來(lái)表示算術(shù)表達(dá)式。可以用樹(shù)來(lái)表示算術(shù)表達(dá)式。Edatapoint1point2point3ABCDFGHIJroot(a)(b)第五頁(yè)，共26頁(yè)。二叉樹(shù)一種特殊的樹(shù)型結(jié)構(gòu)二叉樹(shù)一種特殊的樹(shù)型結(jié)構(gòu)(jigu)(jigu)，特點(diǎn)是樹(shù)中，特點(diǎn)是樹(shù)中每個(gè)結(jié)點(diǎn)只有兩棵子樹(shù)，且子樹(shù)有左右之分，

5、次序不每個(gè)結(jié)點(diǎn)只有兩棵子樹(shù)，且子樹(shù)有左右之分，次序不能顛倒。能顛倒。因?yàn)闃?shù)的每個(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對(duì)樹(shù)的處理因?yàn)闃?shù)的每個(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對(duì)樹(shù)的處理算法很復(fù)雜。所以引出二叉樹(shù)的討論。算法很復(fù)雜。所以引出二叉樹(shù)的討論。第六頁(yè)，共26頁(yè)。 空二叉樹(shù)空二叉樹(shù) 僅有僅有根結(jié)點(diǎn)根結(jié)點(diǎn) 右子樹(shù)右子樹(shù)為空為空 左子樹(shù)左子樹(shù)為空為空左右子樹(shù)左右子樹(shù)均非空均非空第七頁(yè)，共26頁(yè)。二叉樹(shù)的第二叉樹(shù)的第i i層上至多有層上至多有2i-12i-1（i i1 1）個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)(ji din)(ji din)。深度為深度為m m的二叉樹(shù)中至多含有的二叉樹(shù)中至多含有2m-12m-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji di

6、n)(ji din)。若在任意一棵二叉樹(shù)中，有若在任意一棵二叉樹(shù)中，有n0n0個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)(ji din)(ji din)，有，有n2n2個(gè)度為個(gè)度為2 2的結(jié)點(diǎn)的結(jié)點(diǎn)(ji din)(ji din)，則：，則：n0=n2+1n0=n2+1A AB BC CD DE EF F第八頁(yè)，共26頁(yè)。性質(zhì)性質(zhì)1 1：二叉樹(shù)的第：二叉樹(shù)的第i i層上至多有層上至多有2 i-12 i-1（i i 1 1）個(gè)結(jié)點(diǎn)。）個(gè)結(jié)點(diǎn)。證明：根據(jù)二叉樹(shù)的特點(diǎn)，結(jié)論證明：根據(jù)二叉樹(shù)的特點(diǎn)，結(jié)論(jiln)(jiln)是顯然的。是顯然的。性質(zhì)性質(zhì)2 2：深度為：深度為m m的二叉樹(shù)中至多的二叉樹(shù)中至多(zhdu)(

7、zhdu)含有含有2m-12m-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。證明：深度為證明：深度為m m的二叉樹(shù)最多有的二叉樹(shù)最多有m m層，根據(jù)性質(zhì)層，根據(jù)性質(zhì)1 1，只要將第，只要將第1 1層到第層到第m m層層的最大結(jié)點(diǎn)數(shù)相加，就可得到整個(gè)二叉樹(shù)中結(jié)點(diǎn)的最大值。的最大結(jié)點(diǎn)數(shù)相加，就可得到整個(gè)二叉樹(shù)中結(jié)點(diǎn)的最大值。21-1+22-21-1+22-1+2m-1=2m-1 1+2m-1=2m-1 性質(zhì)性質(zhì)3 3：度為：度為0 0的結(jié)點(diǎn)總比度為的結(jié)點(diǎn)總比度為2 2的結(jié)點(diǎn)多一個(gè)的結(jié)點(diǎn)多一個(gè)(y )(y )。設(shè)：有設(shè)：有n0n0個(gè)葉子結(jié)點(diǎn)，有個(gè)葉子結(jié)點(diǎn)，有n1n1個(gè)度為個(gè)度為1 1的結(jié)點(diǎn)，有的結(jié)點(diǎn)，有n2n2個(gè)度為個(gè)度為2

8、 2的結(jié)點(diǎn)，的結(jié)點(diǎn)， 則二叉樹(shù)中結(jié)點(diǎn)總數(shù)為：則二叉樹(shù)中結(jié)點(diǎn)總數(shù)為：n=n0+n1+n2 n=n0+n1+n2 設(shè)所有進(jìn)入分支的總數(shù)為設(shè)所有進(jìn)入分支的總數(shù)為m,m,則總的結(jié)點(diǎn)個(gè)數(shù)為：則總的結(jié)點(diǎn)個(gè)數(shù)為：n=m+1n=m+1總的射出分支與總的進(jìn)入分支數(shù)相等：總的射出分支與總的進(jìn)入分支數(shù)相等：m=n1+2n2 m=n1+2n2 因此：因此： n0+n1+n2=n1+2n2+1 n0+n1+n2=n1+2n2+1 所以：所以： n0= n2+1 n0= n2+1 A AB BC CD DE EF F4 42 23 31 15 56 67 78 89 9101011111212131314141515A

9、AB BC CD DE EF FA AB BC CD DE EF F4 42 23 31 15 56 67 78 89 9101011111212131314141515用歸納法證明：用歸納法證明： i=1i=1，則結(jié)點(diǎn)數(shù)，則結(jié)點(diǎn)數(shù)=2=20 0 =1=1為根結(jié)點(diǎn)。為根結(jié)點(diǎn)。若已知若已知 i-1i-1層上結(jié)點(diǎn)數(shù)至多有層上結(jié)點(diǎn)數(shù)至多有2 2(i-1)-1(i-1)-1=2=2i-2i-2 個(gè)，由于二叉樹(shù)每個(gè)個(gè)，由于二叉樹(shù)每個(gè)結(jié)點(diǎn)度數(shù)最大為結(jié)點(diǎn)度數(shù)最大為2 2，因此第，因此第i i層上結(jié)點(diǎn)數(shù)最多為第層上結(jié)點(diǎn)數(shù)最多為第i-1i-1層上結(jié)點(diǎn)數(shù)層上結(jié)點(diǎn)數(shù)的的2 2倍，即倍，即2 22 2i-2i-2=2

10、=2i-1i-1。第九頁(yè)，共26頁(yè)。4 42 23 31 15 56 67 78 89 91010111112121313141415154 42 23 31 15 56 67 78 89 9101011111212完全完全(wnqun)(wnqun)二二叉樹(shù)叉樹(shù)4 42 23 31 15 56 67 78 89 9101011111212非完全二叉樹(shù)非完全二叉樹(shù)第十頁(yè)，共26頁(yè)。(2) (2) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)(cn ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu)T16若父結(jié)點(diǎn)在數(shù)組中若父結(jié)點(diǎn)在數(shù)組中i i下標(biāo)下標(biāo)(xi bio)(xi bio)處，其左孩子在處，其左孩子在2 2* *i i處，右孩子在處，右

11、孩子在2 2* *i+1i+1處。處。1111 A A B BC C F F E E D D 1 1 2 2 4 8 8 9 91010 5 5 6 6 3 3 7 71212131314141515(1) (1) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)(1) (1) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)2 2h h-1=-1=2 24 4-1 = 15-1 = 15用一組連續(xù)的存儲(chǔ)單元存放二用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組叉樹(shù)的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹(shù)

12、必須按完全二叉樹(shù)的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。一般二叉樹(shù)必須按完全二叉樹(shù)的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。第十一頁(yè)，共26頁(yè)。rchildrchildDataDatalchildlchild A AD DB B C C E E F F 圖為一般圖為一般(ybn)(ybn)二叉樹(shù)的二叉鏈二叉樹(shù)的二叉鏈表結(jié)構(gòu)表結(jié)構(gòu)AECBDF第十二頁(yè)，共26頁(yè)。鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)(cn ch)結(jié)構(gòu)的算法描述：結(jié)構(gòu)的算法描述：Typedef struct BiTNode int data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;rchildDatalchil

13、drchildDatalchildrchildDatalchild第十三頁(yè)，共26頁(yè)。樹(shù)的結(jié)點(diǎn)個(gè)數(shù)至少為樹(shù)的結(jié)點(diǎn)個(gè)數(shù)至少為1 1，而二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可以，而二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可以(ky)(ky)為為0 0。樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)最大度數(shù)為樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)最大度數(shù)為2 2。樹(shù)的結(jié)點(diǎn)子樹(shù)無(wú)左、右之分，二叉樹(shù)的結(jié)點(diǎn)子樹(shù)有明確的左、樹(shù)的結(jié)點(diǎn)子樹(shù)無(wú)左、右之分，二叉樹(shù)的結(jié)點(diǎn)子樹(shù)有明確的左、 右之分。右之分。 二叉樹(shù)二叉樹(shù)樹(shù)樹(shù)第十四頁(yè)，共26頁(yè)。子之間的聯(lián)系；子之間的聯(lián)系；以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)以根結(jié)點(diǎn)為軸心，將整個(gè)樹(shù)順時(shí)針轉(zhuǎn)4545度。度。第十五頁(yè)，共26頁(yè)。

14、 A B CD E G H FI(a)ABEFCDGHI(d) I A B C DE F G H(b)ABCDEFGHI(c)第十六頁(yè)，共26頁(yè)。ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：將各棵樹(shù)分別轉(zhuǎn)成二叉樹(shù)；將各棵樹(shù)分別轉(zhuǎn)成二叉樹(shù)；把每棵樹(shù)的根結(jié)點(diǎn)用線(xiàn)連起來(lái)；把每棵樹(shù)的根結(jié)點(diǎn)用線(xiàn)連起來(lái)；以第一棵樹(shù)的根結(jié)點(diǎn)作為二叉樹(shù)的以第一棵樹(shù)的根結(jié)點(diǎn)作為二叉樹(shù)的根結(jié)點(diǎn)，按順時(shí)針?lè)较蚋Y(jié)點(diǎn)，按順時(shí)針?lè)较?fngxing)(fngxing)旋轉(zhuǎn)。旋轉(zhuǎn)。第十七頁(yè)，共26頁(yè)。中序遍歷中序遍歷(L D R):(L D R):按中序遍歷左子樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)，按按中序遍歷

15、左子樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。中序遍歷右子樹(shù)。后序遍歷后序遍歷(L R D):(L R D):按后序遍歷左子樹(shù)，按后序遍歷右子按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)。樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)。二叉樹(shù)為空時(shí)，執(zhí)行空操作，即空二叉二叉樹(shù)為空時(shí)，執(zhí)行空操作，即空二叉樹(shù)已遍歷完。樹(shù)已遍歷完。第十八頁(yè)，共26頁(yè)。先序遍歷先序遍歷(bin l)(bin l)：D L RD L R中序遍歷中序遍歷(bin l)(bin l)：L D RL D R后序遍歷后序遍歷(bin l)(bin l)：L R DL R DA AD DB BC CT T1 1T T2 2T T3 3D L RD L RA AD L

16、 RD L RD L RD L R B B D D C CD L RD L R以先序遍歷以先序遍歷(bin (bin l)D L Rl)D L R為例演示為例演示遍歷遍歷(bin l)(bin l)過(guò)程過(guò)程 ABDCABDCBDACBDAC DBCA DBCA第十九頁(yè)，共26頁(yè)。先序遍歷先序遍歷(bin l)(bin l)二叉樹(shù)的遞歸算法：二叉樹(shù)的遞歸算法： void PreOderTraverse(BiTree T)void PreOderTraverse(BiTree T) if(T! =NULL) if(T! =NULL) printf (T-data); printf (T-data)

17、; PreOrderTraverse(T-lchild); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); PreOrderTraverser(T-rchild); 第二十頁(yè)，共26頁(yè)。第二十一頁(yè)，共26頁(yè)。/ /* *建立建立(jinl)(jinl)二叉鏈表，并進(jìn)行二叉樹(shù)的遍歷二叉鏈表，并進(jìn)行二叉樹(shù)的遍歷* */ /#include stdio.h#include stdio.h#include stdlib.h#include stdlib.hstruct btnodestruct btnode int d; int d;

18、struct btnode struct btnode * *lchild;lchild; struct btnode struct btnode * *rchild;rchild;intrav(struct btnode intrav(struct btnode * *bt)bt) if(bt!=NULL) if(bt!=NULL) pretrav(bt-lchild); pretrav(bt-lchild); printf(%dn,bt-d); printf(%dn,bt-d); pretrav(bt-rchild); pretrav(bt-rchild); return; return;

19、 main()main() struct btnode struct btnode * *bt,bt,* *h;h; bt=create(h,0); bt=create(h,0); pretrav(bt); pretrav(bt); struct btnode *create(bt,k)struct btnode *bt;int k; char b; struct btnode *p,*t; printf(input b:); scanf(%d,&b); if(b!=0) p=(struct btnode *)malloc(sizeof(struct btnode); p-d=b;p-lchild=NULL;p-rchild=NULL; if(k=0) t=p; if(k=1) bt-lchild=p; if(k=2) bt-rchild=p; create(p,1); create(p,2); return