樹與二叉樹復習進程

1、樹（非線性數(shù)據(jù)結(jié)構(gòu)樹（非線性數(shù)據(jù)結(jié)構(gòu)(sh j ji u)）第一頁，共26頁。第二頁，共26頁。 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)實世界中，能用樹的結(jié)構(gòu)表示的例子：現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族學校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族(jiz)(jiz)血緣血緣關(guān)系等。關(guān)系等。計算機軟件技術(shù)中，能用樹的結(jié)構(gòu)表示計算機軟件技術(shù)中，能用樹的結(jié)構(gòu)表示(biosh)(biosh)的例子：的例子：操作系統(tǒng)中的多級文件目錄結(jié)構(gòu)，高級語言中源程序的語法操作

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

3、該結(jié)點的孩子結(jié)點。雙親（雙親（ParentParent）：孩子結(jié)點的上層結(jié)點，稱為這些結(jié)點的雙）：孩子結(jié)點的上層結(jié)點，稱為這些結(jié)點的雙親。親。兄弟兄弟(xingd)(xingd)（SiblingSibling）：同一雙親的孩子。）：同一雙親的孩子。深度（深度（Depth)Depth)： 樹中結(jié)點的最大層次數(shù)。樹中結(jié)點的最大層次數(shù)。森林（森林（ForestForest）：）：M M棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募稀?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第四頁，共26頁。 樹的存儲結(jié)構(gòu)可以采用具有多個指

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

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

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

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

8、 2的結(jié)點，的結(jié)點， 則二叉樹中結(jié)點總數(shù)為：則二叉樹中結(jié)點總數(shù)為：n=n0+n1+n2 n=n0+n1+n2 設(shè)所有進入分支的總數(shù)為設(shè)所有進入分支的總數(shù)為m,m,則總的結(jié)點個數(shù)為：則總的結(jié)點個數(shù)為：n=m+1n=m+1總的射出分支與總的進入分支數(shù)相等：總的射出分支與總的進入分支數(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é)點數(shù)，則結(jié)點數(shù)=2=20 0 =1=1為根結(jié)點。為根結(jié)點。若已知若已知 i-1i-1層上結(jié)點數(shù)至多有層上結(jié)點數(shù)至多有2 2(i-1)-1(i-1)-1=2=2i-2i-2 個，由于二叉樹每個個，由于二叉樹每個結(jié)點度數(shù)最大為結(jié)點度數(shù)最大為2 2，因此第，因此第i i層上結(jié)點數(shù)最多為第層上結(jié)點數(shù)最多為第i-1i-1層上結(jié)點數(shù)層上結(jié)點數(shù)的的2 2倍，即倍，即2 22 2i-2i-2=2

10、=2i-1i-1。第九頁，共26頁。4 42 23 31 15 56 67 78 89 91010111112121313141415154 42 23 31 15 56 67 78 89 9101011111212完全完全(wnqun)(wnqun)二二叉樹叉樹4 42 23 31 15 56 67 78 89 9101011111212非完全二叉樹非完全二叉樹第十頁，共26頁。(2) (2) 鏈式存儲鏈式存儲(cn ch)(cn ch)結(jié)構(gòu)結(jié)構(gòu)T16若父結(jié)點在數(shù)組中若父結(jié)點在數(shù)組中i i下標下標(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) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)(1) (1) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)2 2h h-1=-1=2 24 4-1 = 15-1 = 15用一組連續(xù)的存儲單元存放二用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間中的相對位置蘊含著結(jié)點之間的關(guān)系。的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹

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

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

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

15、左子樹，訪問根結(jié)點，按中序遍歷右子樹。中序遍歷右子樹。后序遍歷后序遍歷(L R D):(L R D):按后序遍歷左子樹，按后序遍歷右子按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。樹，訪問根結(jié)點。二叉樹為空時，執(zhí)行空操作，即空二叉二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。樹已遍歷完。第十八頁，共26頁。先序遍歷先序遍歷(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)過程過程 ABDCABDCBDACBDAC DBCA DBCA第十九頁，共26頁。先序遍歷先序遍歷(bin l)(bin l)二叉樹的遞歸算法：二叉樹的遞歸算法： 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); 第二十頁，共26頁。第二十一頁，共26頁。/ /* *建立建立(jinl)(jinl)二叉鏈表，并進行二叉樹的遍歷二叉鏈表，并進行二叉樹的遍歷* */ /#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