部分地包含自身，直接或間接地調(diào)用自身定義遞歸：longFactor(longn){if(n==0)return1;elsereturnn*Factor(n-1);}參數(shù)計(jì)算返回00！=11

參數(shù)計(jì)算返回11*Factor(0)

參數(shù)計(jì)算返回22*Factor(1)

參數(shù)計(jì)算返回33*Factor(2)

主程序main()32101266部分地包含自身，直接或間接地調(diào)用自身定義遞歸：longFa1數(shù)據(jù)結(jié)構(gòu)遞歸:typedefstructtNode{

Elemtypedata;

tNode*next;

}tNode,*link;

tNodenewnode;

linklist;數(shù)據(jù)結(jié)構(gòu)遞歸:typedefstructtNode{

2樹n個(gè)結(jié)點(diǎn)的有限集合,n>1,T:1.一個(gè)根結(jié)點(diǎn)root2.1245673n=0n=11樹n個(gè)結(jié)點(diǎn)的有限集合,n>1,T:1.一個(gè)根結(jié)點(diǎn)root23abdefgc樹的術(shù)語(yǔ)結(jié)點(diǎn)=數(shù)據(jù)項(xiàng)+分枝結(jié)點(diǎn)的度葉、分支、子女、雙親、兄弟

祖先、子孫結(jié)點(diǎn)所處層次樹的高度樹的度有序樹、無(wú)序樹森林abdefgcadgabdefgc樹的術(shù)語(yǔ)結(jié)點(diǎn)=數(shù)據(jù)項(xiàng)+分枝結(jié)點(diǎn)的度葉、分支、子4二叉樹n個(gè)結(jié)點(diǎn)的集合，T：,n=0T左+T右，n>0T=

(a)空二叉樹AABABACB(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹二叉樹n個(gè)結(jié)點(diǎn)的集合，T：,n=0T左+T右，n5二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)2453671當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20=1,命題成立。對(duì)于j=i-1,假定命題成立，則第j層上至多有2j-1個(gè)結(jié)點(diǎn)，故第j+1層上最多有2j-1*2即2j個(gè)結(jié)點(diǎn)，即第i層上最多有2i-1個(gè)結(jié)點(diǎn)。證畢。二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)6性質(zhì)3：對(duì)任何一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。性質(zhì)2：深度為k的二叉樹至多有2k－1個(gè)結(jié)點(diǎn)（k>=1).證明：設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為n1，有：

N＝n0＋n1＋n2(1)設(shè)B為二叉樹中的分支總數(shù)，則有B=N-1，同時(shí)B=n1+2n2,于是有

N=n1+2n2-1(2)故

n0＝n2＋12453671性質(zhì)3：對(duì)任何一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)n0，度性質(zhì)2：深7滿二叉樹:深度為k且共有2k-1個(gè)結(jié)點(diǎn)12345612345712367(a)完全二叉樹(b)非完全二叉樹(c)非完全二叉樹2453671完全二叉樹葉結(jié)點(diǎn)出現(xiàn)在最高或次高層對(duì)于任意結(jié)點(diǎn),如果C(Tr)=s,則C(Tl)=s或s+1滿二叉樹:深度為k且共有2k-1個(gè)結(jié)點(diǎn)123456123458性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為123452k-1－1<n<=2k-12k-1<=n<2k性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為123452k-1－9性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)從高到低從左到右編號(hào),則對(duì)任一結(jié)點(diǎn)i,有：1）i＝1，則i無(wú)雙親，是根；i>1，則雙親【i/2】;2)2i>n，則i為葉子；否則，其左孩子是2i;3）如果2i＋1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i＋1。123456123452453671性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)從高到低從左10遍歷二叉樹2453671LDR

DLR——先（根）序遍歷

LDR——中（根）序遍歷LRD——后（根）序遍歷遍歷二叉樹2453671LDRDLR——先（根）序遍11二叉樹表達(dá)式(a+b*(c-d)-e/f)－＋*a/b-dcfe其先序序列為：-+a*b-cd/ef

其中序序列為：a+b*c-d-e/f其后序序列為：abcd-*+ef/-二叉樹表達(dá)式－＋*a/b-dcfe其先序序列為：12鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)13

typedefstructBiTNode{

Elemtypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

typedefstructBiTNode{

Elem14BiTreeCreate(BiTreeT){charch;cin>>ch;if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))cout<<"Error!";T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}returnT;}ABC##DE#G##F###T^^^^^^^^BiTreeCreate(BiTreeT)ABC##DE15-+a##*b##-c##d##/e##f##－＋*a/b-dcfe-+a##*b##-c##d##/e##f##－＋*a/b-16前序遍歷voidPreorder(BiTreeT){if(T){cout<<T->data;Preorder(T->lchild);Preorder(T->rchild);}}－＋*a/b-dcfe前序遍歷voidPreorder(BiTreeT){－17葉結(jié)點(diǎn)個(gè)數(shù)intSumleaf(BiTreeT){intsum=0,m,n;if(T){if((!T->lchild)&&(!T->rchild))sum++;m=Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;}returnsum;}－＋*a/b-dcfe葉結(jié)點(diǎn)個(gè)數(shù)intSumleaf(BiTreeT){－＋18intDepth(BiTreeT){intdep=0,depl,depr;if(!T)dep=0;else{depl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);}returndep;}－＋*a/b-dcfe樹的深度intDepth(BiTreeT){－＋*a/b-dc19線索化二叉樹^^^^^^中序遍歷BDAEC^^線索化二叉樹^^^^^^中序遍歷BDAEC^^20中序遍歷BDAEC^^中序遍歷BDAEC^^21樹的存儲(chǔ)表示cefdhjabgklim樹的存儲(chǔ)表示cefdhjabgklim22森林轉(zhuǎn)化為二叉樹cefdhjabgki森林轉(zhuǎn)化為二叉樹cefdhjabgki23路徑長(zhǎng)度：結(jié)點(diǎn)間的分支數(shù)24536718241368570,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4….0,1,1,2,2,2,3,3n個(gè)結(jié)點(diǎn),高為k,從根到k-1層最多有2k-1-1個(gè)點(diǎn)，其余分布在第k層，最小路徑長(zhǎng)度路徑長(zhǎng)度：結(jié)點(diǎn)間的分支數(shù)24536718241368570,24HuffmanTreeT有n個(gè)葉結(jié)點(diǎn)，權(quán)值w0,…wn-1,擴(kuò)充二叉樹T的帶權(quán)路徑長(zhǎng)度：245724577524WPL最小的二叉樹HuffmanTreeT有n個(gè)葉結(jié)點(diǎn)，權(quán)值w0,…wn-125構(gòu)造HuffmanTree245761118CASTCASTSATATATASAC,A,S,T:2,7,4,5245761118011100A:0,T:10,C:110,S:111構(gòu)造HuffmanTree245761118CASTC26精品課件！精品課件！27精品課件！精品課件！2824576111801110024576111801110029部分地包含自身，直接或間接地調(diào)用自身定義遞歸：longFactor(longn){if(n==0)return1;elsereturnn*Factor(n-1);}參數(shù)計(jì)算返回00！=11

參數(shù)計(jì)算返回11*Factor(0)

參數(shù)計(jì)算返回22*Factor(1)

參數(shù)計(jì)算返回33*Factor(2)

主程序main()32101266部分地包含自身，直接或間接地調(diào)用自身定義遞歸：longFa30數(shù)據(jù)結(jié)構(gòu)遞歸:typedefstructtNode{

Elemtypedata;

tNode*next;

}tNode,*link;

tNodenewnode;

linklist;數(shù)據(jù)結(jié)構(gòu)遞歸:typedefstructtNode{

31樹n個(gè)結(jié)點(diǎn)的有限集合,n>1,T:1.一個(gè)根結(jié)點(diǎn)root2.1245673n=0n=11樹n個(gè)結(jié)點(diǎn)的有限集合,n>1,T:1.一個(gè)根結(jié)點(diǎn)root232abdefgc樹的術(shù)語(yǔ)結(jié)點(diǎn)=數(shù)據(jù)項(xiàng)+分枝結(jié)點(diǎn)的度葉、分支、子女、雙親、兄弟

祖先、子孫結(jié)點(diǎn)所處層次樹的高度樹的度有序樹、無(wú)序樹森林abdefgcadgabdefgc樹的術(shù)語(yǔ)結(jié)點(diǎn)=數(shù)據(jù)項(xiàng)+分枝結(jié)點(diǎn)的度葉、分支、子33二叉樹n個(gè)結(jié)點(diǎn)的集合，T：,n=0T左+T右，n>0T=

(a)空二叉樹AABABACB(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹二叉樹n個(gè)結(jié)點(diǎn)的集合，T：,n=0T左+T右，n34二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)2453671當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20=1,命題成立。對(duì)于j=i-1,假定命題成立，則第j層上至多有2j-1個(gè)結(jié)點(diǎn)，故第j+1層上最多有2j-1*2即2j個(gè)結(jié)點(diǎn)，即第i層上最多有2i-1個(gè)結(jié)點(diǎn)。證畢。二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)35性質(zhì)3：對(duì)任何一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。性質(zhì)2：深度為k的二叉樹至多有2k－1個(gè)結(jié)點(diǎn)（k>=1).證明：設(shè)二叉樹中度為1的結(jié)點(diǎn)數(shù)為n1，有：

N＝n0＋n1＋n2(1)設(shè)B為二叉樹中的分支總數(shù)，則有B=N-1，同時(shí)B=n1+2n2,于是有

N=n1+2n2-1(2)故

n0＝n2＋12453671性質(zhì)3：對(duì)任何一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)n0，度性質(zhì)2：深36滿二叉樹:深度為k且共有2k-1個(gè)結(jié)點(diǎn)12345612345712367(a)完全二叉樹(b)非完全二叉樹(c)非完全二叉樹2453671完全二叉樹葉結(jié)點(diǎn)出現(xiàn)在最高或次高層對(duì)于任意結(jié)點(diǎn),如果C(Tr)=s,則C(Tl)=s或s+1滿二叉樹:深度為k且共有2k-1個(gè)結(jié)點(diǎn)1234561234537性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為123452k-1－1<n<=2k-12k-1<=n<2k性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為123452k-1－38性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)從高到低從左到右編號(hào),則對(duì)任一結(jié)點(diǎn)i,有：1）i＝1，則i無(wú)雙親，是根；i>1，則雙親【i/2】;2)2i>n，則i為葉子；否則，其左孩子是2i;3）如果2i＋1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則，其右孩子是結(jié)點(diǎn)2i＋1。123456123452453671性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)從高到低從左39遍歷二叉樹2453671LDR

DLR——先（根）序遍歷

LDR——中（根）序遍歷LRD——后（根）序遍歷遍歷二叉樹2453671LDRDLR——先（根）序遍40二叉樹表達(dá)式(a+b*(c-d)-e/f)－＋*a/b-dcfe其先序序列為：-+a*b-cd/ef

其中序序列為：a+b*c-d-e/f其后序序列為：abcd-*+ef/-二叉樹表達(dá)式－＋*a/b-dcfe其先序序列為：41鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)42

typedefstructBiTNode{

Elemtypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

typedefstructBiTNode{

Elem43BiTreeCreate(BiTreeT){charch;cin>>ch;if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))cout<<"Error!";T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}returnT;}ABC##DE#G##F###T^^^^^^^^BiTreeCreate(BiTreeT)ABC##DE44-+a##*b##-c##d##/e##f##－＋*a/b-dcfe-+a##*b##-c##d##/e##f##－＋*a/b-45前序遍歷voidPreorder(BiTreeT){if(T){cout<<T->data;Preorder(T->lchild);Preorder(T->rchild);}}－＋*a/b-dcfe前序遍歷voidPreorder(BiTreeT){－46葉結(jié)點(diǎn)個(gè)數(shù)intSumleaf(BiTreeT){intsum=0,m,n;if(T){if((!T->lchild)&&(!T->rchild))sum++;m=Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;}returnsum;}－＋*a/b-dcfe葉結(jié)點(diǎn)個(gè)數(shù)intSumleaf(BiTreeT){－＋47intDepth(BiTreeT){intdep=0,depl,depr;if(!T)dep=0;else{depl=Depth(T->lchild);depr=D