11AABCDEFGHIJ樹(shù)是遞歸結(jié)構(gòu)，樹(shù)的定義是遞歸定義 的有限集T1T2Tm，其中每一棵子集本身又是3棵樹(shù)T。

HIT={A，B，C，D，E，F(xiàn)，G，H，I，JA是根，其余結(jié)點(diǎn)可以劃分為3個(gè)互不相交的T1={B,E,F T2={C,G}T3={D,H,I,J根A的子樹(shù)。T11=ET12FT11，T12是B的子 HI5血統(tǒng)二叉樹(shù)樹(shù)6C文件夾1?文件夾 文件1?文件文件夾21件夾22件21?文件7DNSDNSName

12345凹入表示法（類似書(shū) A HI96.1表T={A，B，C，D，E，F(xiàn)，G，H，I，JR={<A,B>,<A,C>,<A,D>,<B,E>,<C,G>,<D,H>,<D,I>,<D,J>AABCDEFGHIJ6.1樹(shù)的表樹(shù)的表 AB DH IF J假設(shè)樹(shù)的根為root，子樹(shù)為T(mén)1,T2,?,Tn，與該樹(shù)對(duì)應(yīng)的廣義表為L(zhǎng)，則：L=(原子(子表1,子表2,?,子表n))，其中原子對(duì)應(yīng)rooti(1<i<=nA

(A(B(E,F),C,樹(shù)根 6.1樹(shù)的6.1樹(shù)的ABCGDMABCDABCDEFGHIJKLM結(jié)點(diǎn)的度:分支的個(gè)數(shù)樹(shù)的度:樹(shù)中所有結(jié)點(diǎn)的葉子結(jié)點(diǎn)度為零的

(從根到結(jié)點(diǎn)的)路徑 由從根到該結(jié)經(jīng)分支和結(jié)點(diǎn)

祖先結(jié)點(diǎn)、子孫結(jié) 結(jié)點(diǎn)的層次

假設(shè)根結(jié)點(diǎn)的層次為1,第l層的樹(shù)的深度：樹(shù)中葉子結(jié)點(diǎn)所在的最大6.1FAB6.1FABEFCGHDIKLJM任何一棵非空樹(shù)是一個(gè)二其中：root稱為根結(jié)點(diǎn)，F(xiàn)稱為子樹(shù) InitTree(&T構(gòu)造空樹(shù)TDestroyTree(&TTCreateTree(&T,definitiondefinition構(gòu)造樹(shù)TClearTree(&TTTreeEmpty(TT為空，返回TURE，否則返回FALSETreeDepth(TT樹(shù)的基本Root(TTValue(T,&cur_eTcur_eAssign(T,cur_e,valueTcur_evalueParent(T,cur_eTcur_eLeftChild(T,cur_eTcur_eRightSibling(T,cur_eTcur_eInsertChild(&T,&p,i,ccTpiDeleteChild(&T,&p,iTpiTraverseTree(T,Visit()TVisit()線性第一個(gè)數(shù)據(jù)元(無(wú)前最后一個(gè)數(shù)據(jù)(無(wú)后繼其它數(shù)據(jù)元(一個(gè)前驅(qū)一個(gè)后

樹(shù)型(無(wú)前驅(qū)多個(gè)葉子結(jié)(無(wú)后繼其它數(shù)據(jù)(一個(gè)前多個(gè)后

相交RD＝Φ，則R＝ΦD≠Φ，則R＝{H}，H若D-{root}≠Φ，則存在D-{root}＝{Dl,Dr}，且Dl∩Dr=Φ。

根結(jié) BCD左子

右子EFG NN

NLNLNR只有左子樹(shù)只有右子

NNLR左右子樹(shù)均非說(shuō)明二叉樹(shù)中每個(gè)結(jié)個(gè)結(jié)點(diǎn)度小于等于左、右子樹(shù)不能顛倒——有序樹(shù)二叉二叉ABABCDEFGACBFDEG (a)、(b)(a)的左子樹(shù)有四個(gè)結(jié)點(diǎn)，(b)二叉樹(shù)二叉樹(shù)的 乙甲 甲乙甲 甲乙甲二叉樹(shù)二叉樹(shù)的ABABCDEFG-+/a*efb-cda+b*(c–d)–e/在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)ABCDEFGi=1最多1個(gè)結(jié)點(diǎn)i=2最多2個(gè)結(jié)點(diǎn)i=3ABCDEFG性質(zhì)在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)用歸納法證明歸納基i1層時(shí)，只有一個(gè)根2i-1=20=：假設(shè)對(duì)所j,1≤ji，命題成立；則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1性質(zhì)性質(zhì)深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)(k≥1)證明20+21++2k-1=2k-性質(zhì)性質(zhì)個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0n2+1證明bn-1n0n1n2由此n0n2123456789123456789k且含有2k-個(gè)結(jié)點(diǎn)的二叉abcdefghijn個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1abcdefghij性質(zhì)性質(zhì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1證明設(shè)為則根據(jù)第二條性質(zhì)2k-1≤n即k-1≤log2nk只能是整數(shù)，因此，klog2n性質(zhì)

號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)；否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。iii二叉樹(shù) 順序依 A 4 5 1 34 6

m-ABCDEFA 34 5 F G A 34 5 F G1234 6789 m-ABCDE0F00G

ABCABCABCD

typedefstruct ElemTypestructBiTNode*lchild,*}BiTNode,*數(shù)據(jù)指針數(shù)據(jù)域指指針數(shù)據(jù)域指針指向左

指向右ABCDABCDEFA∧C∧∧B∧E∧∧∧∧B∧E∧∧F∧3.3.typedefstruct ElemTypestructstruct}結(jié)點(diǎn)結(jié)構(gòu)

*lchild,**A AEADBFDBCECE 4.

Lchilddata 2A13C-52A13C-5B--E--F--D4 3 無(wú)左孩子或右孩4.

typedefstructBPTNodeemTypedata;intlchild,rchild;}typedefstructBTreeBNodenodes[MAX_TREE_SIZEintnum_node;introot;}

5.data

結(jié)B2LB2LC2RA-D0LE0RF1LG4L12 4 G5.

typedefstructBPTNodeemTypeintparent;charLRTag;}

typedefstructBPTreeBPTNodenodes[MAX_TREE_SIZEintnum_node;introot;}

遍歷的基本 約定先左約定先左后右，有三種遍歷方法：DLRLDR、LRD，分別根根結(jié)點(diǎn)的次先序遍歷、中序遍歷和后序遍歷令：L：遍歷左子 根結(jié) R：遍歷右子有六種遍歷方法 基本 二叉樹(shù)的先序遍歷先序遍歷 若二叉樹(shù)非 先序遍歷左子樹(shù) 先序遍歷右子樹(shù) 例：先序遍歷二叉根結(jié)點(diǎn)先序遍歷右子DLR的順序遍歷右子二叉樹(shù)的先序遍歷先序遍歷 若二叉樹(shù)非 先序遍歷左子樹(shù) 先序遍歷右子樹(shù) 先序遍歷序列：A,B,D,E,G,C, 二叉樹(shù)的中序遍歷中序遍歷 若二叉樹(shù)非 根結(jié)點(diǎn) 中序遍歷右子樹(shù) 例：中序遍歷二根結(jié)點(diǎn)中序遍歷右子樹(shù)：即按LDR的順序遍歷右子樹(shù)中序遍歷序列：D,B,G,E,A, 二叉樹(shù)的后序遍歷后序遍歷 若二叉樹(shù)非 后序遍歷右子樹(shù) 根結(jié)點(diǎn) 例：后序遍歷二根結(jié)點(diǎn)后序遍歷序列：D,G,E,B,F,C, - 先序遍歷序列：-,+,a,*,b,-中序遍歷序列：a,+,b,*,c,-,d,-后序遍歷序列：a,b,c,d,- 若二若二叉樹(shù)非123先序遍歷左子樹(shù)先序遍歷右子樹(shù)上面先序遍歷的定義等若二叉樹(shù)為空，結(jié)束——基本項(xiàng)（也叫終止項(xiàng)若二叉樹(shù)非空——voidPreOrderTraverse(BiTreeStatus(*Visit)(ElemTypee) //采用二叉鏈表存貯二叉樹(shù)，visit() 結(jié)點(diǎn)的函//本算法先序遍歷以T為根結(jié)點(diǎn)指針的二叉ifT //若二叉樹(shù)不Visit(T->data 根結(jié)PreOrderTraverse(T->lchild,Visit);//先序遍歷T的左PreOrderTraverse(T->rchild,Visit);//先序遍歷T的右子}}AT最簡(jiǎn)單Visit函數(shù)是ATStatus emTypee∧CB{//輸出元素e∧CBoutput(e return ∧E∧E∧∧F∧∧∧F∧Tra(PA)Tra(PA)if}}Tra(PC)ifTra(PC-Tra(PC-}}ifTra(PF-Tra(PF-}}T∧E∧CBA∧D∧∧F∧ABDE∧E∧CBA∧D∧∧F∧∧G∧G∧先序遍歷遞歸算法 voidPreOrderTraverse(BiTreeStatus(*Visit)(ElemTypee) //采用二叉鏈表存貯二叉樹(shù)，visit() 結(jié)點(diǎn)的函//本算法先序遍歷以T為根結(jié)點(diǎn)指針的二叉if(T)if(Visit(T->data) //如 根結(jié)點(diǎn)成功，則繼ifPreOrderTraverse(T->lchild,Visit) ifPreOrderTraverse(T->rchild,Visit) returnOK;returnERROR;}elsereturn}//voidInOrderTraverse(BiTreeStatus(*Visit)(ElemTypee) //采用二叉鏈表存貯二叉樹(shù)，visit() 結(jié)點(diǎn)的函//本算法中序遍歷以Tif(T //若二叉樹(shù)不InOrderTraverse(T->lchild,Visit);//中序遍歷T的左子樹(shù)Visit(T->data)； InOrderTraverse(T->rchild,Visit);//中序遍歷T的右子樹(shù)}}//Tra(PA)

Tra(PB)

ififif{Tra(PD-V(A)V(B)Tra(PB-Tra(PD-}}}}}}ATA∧E∧CB∧D∧∧F∧BGE∧E∧CB∧D∧∧F∧∧G∧G∧voidPostOrderTraverse(BiTreeTStatus(*Visit)(ElemTypee) 結(jié)點(diǎn)的函//本算法后序遍歷以Tif(T //若二叉樹(shù)不PostOrderTraverse(T->lchild,Visit);//后序遍歷左子樹(shù)PostOrderTraverse(T->rchild,Visit);//后序遍歷右子樹(shù)Visit(T->data //根結(jié)}}//結(jié)果：voidleaf(BiTreeT

與先序法比較一下{//二叉鏈表存貯二叉樹(shù)，計(jì)算二叉樹(shù)的葉子結(jié)點(diǎn)//先序遍歷的過(guò)程中進(jìn)行統(tǒng)計(jì)，n=0if(T if(T->lchild==null&&T->rchild==nulln //若T所指結(jié)點(diǎn)為葉子結(jié)Aelse{leaf(T->lchild A}}//}//

leaf(T->rchild∧F∧∧B∧F∧∧BD∧D∧∧E∧{//采用二叉鏈表存貯二叉樹(shù)，返回葉子結(jié)點(diǎn)的個(gè)if(!T)returnreturn1;returnCountleave(T->lchild)+Countleave(T->rchild T∧T∧E∧CBA∧D∧D∧∧F∧∧G∧G∧ 基本思想序序列（設(shè)每個(gè)元素是一個(gè)字符） AABCDEFABCD***E**F**先ABCD***E**F**ABD*F***CE**StatusCreateBiTree(BiTree&T //輸入（在空子樹(shù)處添加字符*的二叉樹(shù)的//先序序列（設(shè)元素均為字符）//建立二叉鏈表，并將該二叉鏈表根結(jié)點(diǎn)指針賦給scanf(&chifch‘*’ 若ch=‘*則表示空子elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}

//建立（根）結(jié)//遞歸構(gòu)造左子樹(shù)//遞歸構(gòu)造右子樹(shù)return}AB*C**D*TAA^B^^B^D^^C^^C^例 ATAB∧C∧DB∧C∧D∧∧E∧F∧∧G∧例 {newTif(!T)newT=NULL;{CopyBiTree(T->lchild,plchild);//左子樹(shù)CopyBiTreeT->rchild,prchild);//右子樹(shù)newT=(BiTree)malloc(sizeof(BiTNode));newT->lchild=plchild;newT->rchild=}}

建立二叉樹(shù) 中序遍歷中序遍歷的非遞A若當(dāng)前結(jié)點(diǎn)有右子樹(shù)，后繼結(jié)點(diǎn)為右子樹(shù)A∧G∧最左下結(jié)點(diǎn)∧G∧T∧D∧

否則后繼結(jié)點(diǎn)為∧EB∧CDBGEAF∧EB∧C∧F∧中序遍歷的非遞？當(dāng)前結(jié)點(diǎn) ATA∧CBDBGEAF∧CB∧E∧∧F∧∧E∧∧F∧∧G∧G∧StatusInTrav(BiTreeT,void(* emType{InitStack(S);while(p||! if{Push(S, {Pop(S,p); p=p->rchild;p指向右子樹(shù)}}//whilereturnOK;}//線索二叉

先序序列：ABDEGC中序序列：DBGEAF

后序序列：DGEBFC 線索二叉

A A∧CB ∧CBD∧GFE D∧GFE中序序列：DBGEAF包含“線索” 結(jié)構(gòu)，稱作“線索鏈”在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域Ltag,0示lchild(p向左孩子的1lchild(p直接前驅(qū)的rtag(p)=0rchild(p指向右孩子1rchild(p直接后繼的線 rtagtypedefenum{link,thread}//link=0,typedefstructBiThrNode{ structBiThrNode*lchild,*rchild; Ltag,Rtag;//左、右標(biāo)志域}BiThrNode，* rtag11

00

頭結(jié)0A00A00B00C00B00C00D10E11F10D10E11F11G11G1當(dāng)前結(jié)點(diǎn)的否則，后繼結(jié)點(diǎn)為右子樹(shù)的最左下結(jié)點(diǎn)②BCDGF③①StatusInTra_ThrT(BiThrTreevoid(*Visit) emTypee){pThrT pwhile(p!=ThrT{whilep->Ltag==linkp=p->lchildVisit(p->data //p->Ltag==while(p->Rtag==Thread&&p->rchild!=ThrTp=p->rchild;Visit(p->data}pp->rchild;}return}//雙親表示類型定#defineMAX_TREEE_SIZEtypedefstruct ElemType //雙親位置}PTNode;typedefstruct PTNodenodes[MAX_TREE_SIZE //r為根的位置，n為結(jié)點(diǎn)} ABCDABCDEFA-A-B0C0D0E2F2G5123GG456

樹(shù)的存貯兩種方式：定長(zhǎng)結(jié)點(diǎn)和不定長(zhǎng)結(jié)點(diǎn)方式2：孩子將樹(shù)中的每個(gè)結(jié)點(diǎn)的孩子排一個(gè)線性表，采用線性鏈表進(jìn)行ABCDABCDEFG同一同一結(jié)孩子結(jié)點(diǎn)數(shù)根的位GE6FD54CB321A123456typedefstruct struct }*typedef ElemType }typedef

CTBoxnodes[MAX_TREE_SIZE n }孩子兄弟表示法類型ty