第三3.0樹的定有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹，稱為根樹中至少有一個(gè)結(jié)點(diǎn)——樹中 是互不相交的集只有根結(jié)點(diǎn)的A 的 的根稱為該結(jié)點(diǎn)的孩雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的深度(depth)——結(jié)點(diǎn)A的孩子結(jié)點(diǎn)B的孩子

葉子結(jié)點(diǎn)I的雙親結(jié)點(diǎn)L的雙親樹的度

結(jié)點(diǎn)B，C，D為兄結(jié)點(diǎn)K，L為兄

樹的深度

結(jié)點(diǎn)F，G為堂兄結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖3.1二叉 每個(gè)結(jié)點(diǎn)至多有二 (即不存在度大于2的結(jié)點(diǎn)二叉樹 有左、右之分，且其次序不能任意顛 空二叉

只有根結(jié)的二叉

為

為

左、均非證明：用歸納法證明

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)

1是對(duì)假設(shè)對(duì)所有j(1j<i)命題成立，即第j層上至多有2j1個(gè)結(jié)則可以證明j=I是命題成立由歸納法假設(shè)，第i-1層至多又二叉樹每個(gè)結(jié)點(diǎn)的度至多為

故命題得

2

性質(zhì)2：深度為k的二叉樹至多有2k1個(gè)結(jié)點(diǎn)k證明：由性質(zhì)1，可得深度為k的二叉樹最大結(jié)點(diǎn)數(shù)kk(第i層的最大結(jié)點(diǎn)數(shù)k

2i1

2k設(shè)n1為二叉樹T中度為1

則其左分支下子孫的最大層次必為l或412312345891234567滿二叉1234123456

完全二叉哪些是完全二叉樹性質(zhì)5：如果對(duì)一棵有個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序 ，則對(duì)任一結(jié)點(diǎn)(1n，有：二叉樹 順 結(jié)實(shí)現(xiàn)：按滿二叉樹的結(jié)點(diǎn)層 ，依次存放二叉樹中的據(jù)元特點(diǎn)結(jié)點(diǎn)間關(guān)系蘊(yùn)含在 位置浪費(fèi)空間，適于存滿二叉樹和完全二叉aabcde0000fg abcde0000fg 鏈 結(jié)二叉鏈 struct structnode*lchild,^AB^ABBD^C^D^C^E^^F^E^^F^G在n在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指^G^三叉鏈 node*lchild,*rchild,ABABCDEFG^G^^F^E^^C^DB^^A樹和二叉樹的遍被且僅被一次，即找一個(gè)完整而有規(guī)律的走法，以 后根（序）遍歷：先依次后根遍歷每 ，然 根結(jié)按層次遍歷： 第一層上的結(jié)點(diǎn)，然后依次遍歷第層，……第n層的結(jié)A HJKLNOM后序遍歷EIFGBCJKNOLMHD層次遍歷：ABCDEFGHIJKLMN先序遍歷： 根結(jié)點(diǎn),然后分別先序遍歷 、中序遍歷：先中序遍歷 ，然 根結(jié)點(diǎn)，最后中遍歷后序遍歷：先后序遍歷左、 ，然 根結(jié)按層次遍歷：從上到下、從左到 各結(jié)D LDR、LRD、RDL、RLD、先序遍歷

ABABCDD D D DD 先序遍歷序列：ABD ABCD ABCD L LL AABCD中序遍歷序列：BDALRDABCDLRDABCD L LL AABCD后序遍歷序列： BC--+/a*efb-cd先序遍歷

-+a*b-cd/e中序遍歷

a+b

c-

-e/后序遍歷層次遍歷

abcd--+/a*e

+ef/-b-cd voidpreorder(JD{{printf("%d\t",bt->data);}TBTB

左是空返 返返左是空返TD TD T T 返主程返Pre(T先序序列

T T 返返返T DT返返P-P- 中序非遞P-P-P- P- i

G

P-P-P-P-P-P-P- G

P-P-P-P-P-P- ：C：C：C：CG

P-P-P-P-P-P-P- ：C ：C pG

：CB：CBP-P-P-P-P-P-P- ：CBE ：CBEGAp

：C：CBP-P-B

P-P-P-P- i：CBEG：CBEG：CBEG

pAB P-i P-i

：C：CBEGD

：C：CBEGDFAB G

：CBEGDF按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列ABCDEFG^AABCDEGABCDEFG^A統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)BBDE^^C^求二叉樹深度DE^^C^^F^F^^G^作業(yè)3.7習(xí)題 4 13.2前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個(gè)相的結(jié)點(diǎn)互稱為線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針稱為線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫線索化：對(duì)二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定有n+1個(gè)空鏈索二叉樹的結(jié)點(diǎn)中增加兩個(gè)標(biāo)lt:lt0lclt=1lc域指向其前rt:rt0rc域指向右孩子；若rt=1rc域指向其后結(jié)點(diǎn)定typedefstructintlt,structnode*lc,ABDABDCE0D11C1C11E1^T0B10A0先序T0B10A0先序線索二叉ABDCEABDCE^1B00D1^T1E11C1T1E11C10A0中序線索二叉ABDABDCET1E11C1^1D00B10A0后序序列后序線索二叉 0A00A0^1B00^1B00D1^0A0A01C111C11E1011D00B1頭1D00B1lt=0,lc指向根結(jié)rt=1,rc指向遍歷序列中最后一個(gè)結(jié)

1C1C11E1中序序列結(jié)點(diǎn)的中序線索二叉ABDCEP-JDABDCEP-{JDintt=(JD t->lt=0;t- t- t- {t->lc=bt; t t p0A0 s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p-^0B00D0^^0B00D0^}^0C0^^0E^0C0^^0E0^}}ABDCEP-P-ABDCEP-P-{JDintt=(JD t->lt=0;t- t-{t->lc=bt; tptp0A010 s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- pr->rt=1;pr-^0B00^0B00D0^}^0C0^^0E^0C0^^0E0^}}ABDCEP-ABDCEP-P-{JDintt=(JD t->lt=0;t- t- t- {t->lc=bt; t0A01t0A010 p=s[--printf("%c",p- p->lt=1;p- pr->rt=1;pr->rc=p;} }pr->rc=t;pr->rt=1;t-}

^0B^0B00D0^^0C0^^0C0^^0E0^}JD*zxxsh(JDJD*zxxsh(JD{JDintt=(JD*)malloc(sizeof(JD));t->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}ABDABDCEP-ttP0B1^0A0100D0^^0C^0C0^^0E0^輸出ABDCEJD*zxxsh(JDABDCEP-P-{P-P-intt=(JD t->lt=0;t- t- t- {t->lc=bt; tP0B1tP0B10A010 p=s[--printf("%c",p- p->lt=1;p- pr->rt=1;pr-0D0^0D0^}pr->rc=t;pr->rt=1;t-^0C^0C0^^0E0^輸出輸出}JDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-P-t0t0B10A010輸出0D0^^0^0C0^^0E0^JD*zxxsh(JDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-ttP輸出B^0C1^0B10A0100D0^^0E0^JDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-t0B1t0B10A010輸出B0D0^1C1C0^^0E0^JD*zxxsh(JD{JD叉int叉t=(JD t->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- pr->rt=1;pr->rc=p;}

AABDCEt0 101 00A00B10B10D0^ pr->rc=t;pr->rt=1;t-^1C1^1C1^0E0^}

出BCJDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-1C1C10D00B10A010^ttPP^0E0^輸輸出BCJD*zxxsh(JDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-P-ttP1C10B10A0100D0^^0E0^輸輸出BCJDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-P-tt1C10B10A0100D0^^0E0^輸出B輸出BCJDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-ttP^0E1^1C10B10A0100D0^輸輸出BCAJDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEP-tt1C10B10A0100D0^1E0^輸出輸出BCAJDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCE^1E11C10D00B10A010P^itit輸輸出:BCA JDJD*zxxsh(JD{JDintt->lt=0;t->rt=1; {t->lc=bt; s[i++]=p;p=p->lc; p=s[--printf("%c",p- p->lt=1;p- }pr->rc=t;pr->rt=1;t-}}叉ABD叉ABDCEit010100A00B0B1^1D01E11E11C1輸輸出:BCA ABDABDCE1E11C11D00B1E11C11D00B10A0t01輸出:輸出:BCA 0算 01按中序線索化二叉10A0遍歷中序線索二0A01D01D01B01E11E11C1中序序列 結(jié)點(diǎn)的中序線索二叉在中序線索二叉樹中找結(jié)點(diǎn)后繼的方法若rt=1,則rc域直接指向其后若rt=0,則結(jié)點(diǎn)的后繼應(yīng)是其 的左鏈尾（lt=1)的結(jié)在中序線索二叉樹中找結(jié)點(diǎn)前驅(qū)的方法若lt=1,則lc域直接指向其前若lt=0,則結(jié)點(diǎn)的前驅(qū)應(yīng)是其 的右鏈尾（rt=1)的結(jié)6.4樹 結(jié)樹 結(jié)實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域數(shù)據(jù)域：存放結(jié)點(diǎn)本身信雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中特點(diǎn)：找雙親容易，找孩子typedefstruct intparent; abcdefgabcdefghi0號(hào)單元不用存結(jié)點(diǎn)個(gè)09a0b1c1d2e2f3g5h5i5012345678如何如何找孩子結(jié)

，反復(fù)調(diào)用到樹的多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向 的結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹的度結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈 ，再用含n元素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈孩子結(jié)點(diǎn) int //該結(jié)點(diǎn)在表頭數(shù)組中下structnode //指向下一孩子結(jié)表頭結(jié)點(diǎn) struct //數(shù)據(jù)structnode //指向第一個(gè)孩子結(jié) //t[0]不abc3^5^abc3^5^ f01a2 i2b43c6^4d^5e789^6f^g^7h^8如何找雙親結(jié)9i^帶雙親的孩子ahi01ahi011223555^^^^^7^64298abcdefghi123456789

3^5^^^孩子兄弟表示法（二叉鏈表表示法個(gè)孩子和下一個(gè)兄弟結(jié)點(diǎn)TypedefstructCSNode{ StructCSNodeabcd^eabcdefgabcd^eabcdefghi^^^^^f^hh^g^^i^CB^^ACCB^^ACB^^A

ABCDABCDE^D^^E^^D^^E^ABCABCEDCBCB^^A^E^^D^^D^^D^^E^加線：在兄弟之間加一連抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩間的關(guān)旋轉(zhuǎn)：以樹的根結(jié)點(diǎn) ，將整樹順時(shí)針轉(zhuǎn)A

AB D H樹轉(zhuǎn)換成的二叉樹其 一定為I加線：若的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹

將各棵樹分別轉(zhuǎn)換成二叉將每棵樹的根結(jié)點(diǎn)用線相以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn) ，順針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)A

J A JABCABCD抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支到的所有右孩子間連線全部抹掉，使之變成孤立的二叉還原：將孤立的二叉樹還原ABECABECFGDHIJABECFGDHIEGJFHIJAEBFCDGHIJ樹和森林的遍先序遍歷樹：ABCD后序遍歷樹：BDCE先序遍歷森

D森林中第一棵樹的根節(jié)

先序遍歷第一棵樹中根節(jié)點(diǎn) 森 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的ABCDEFGHI中序遍歷森中序遍歷森林中第一棵樹的根節(jié)點(diǎn) 森第一棵樹的根節(jié)中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的BCDAFEHJI當(dāng)以二叉鏈表做樹 結(jié)構(gòu)時(shí)，樹的先根遍歷和后根遍歷借用二叉樹的先序遍歷和中序遍歷的算法實(shí)現(xiàn)若它的 不空，則 上所有結(jié)點(diǎn)的值均小于它的結(jié)點(diǎn)的若它的 不空，則 上所有結(jié)點(diǎn)的值均大于或等它的根結(jié)點(diǎn)的它的左、 也分別為二叉排序原則：若二叉排序樹為空， 結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)否則，繼續(xù)在其左、 上查找，直至某個(gè)結(jié)點(diǎn)的或 為空為止， 結(jié)點(diǎn)應(yīng)為該結(jié)點(diǎn)的左孩子或右*二叉排序樹生成：從空樹出發(fā)，經(jīng)過一系列的查找 作之后，可生成一棵二叉排算例{1018381227

8

87

87中序中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序要?jiǎng)h除二叉排序樹中的pp為葉子結(jié)點(diǎn)，只需修改p雙親f的指針ff-p只有 或p只有 ，用p的左孩子代替 p只有 ，用p的右孩子代替 p左、 均非 若C無 ，用C取代 SPQ SPQSQ中序遍歷 PS

中序遍歷 SSQP SQPSQ中序遍歷：QSPL

中序遍歷：QSSPQ SPQSQ中序遍歷：PPRS

中序遍歷 SSQP SQPSQ中序遍歷：QSP

中序遍歷：QS中序遍歷 C Q SPPRFSFSCQFPCFPCQSFPC

中序遍歷 C Q SPR FCFC中序遍歷 CPPR

中序遍歷 CPr例 60例 60刪70707054刪除8454刪除845樹(Huffman)——帶權(quán)路徑長度最短的結(jié)點(diǎn)間的~路徑長度：路徑上的分支樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點(diǎn)的路徑長度之

nnk

wkl

—權(quán)l(xiāng)k

fmn樹——設(shè)有個(gè)權(quán)值{}，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子的權(quán)值為則最小的二叉樹叫~例有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二

WKabcdnkabcdncdcdab