數(shù)據(jù)結(jié)構(gòu)遞歸樹(shù)

數(shù)據(jù)結(jié)構(gòu)遞歸樹(shù)第一頁(yè)，共二十八頁(yè)，編輯于2023年，星期三部分地包含自身，直接或間接地調(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第二頁(yè)，共二十八頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)遞歸:typedefstructtNode{

Elemtypedata;

tNode*next;

}tNode,*link;

tNodenewnode;

linklist;^^^第三頁(yè)，共二十八頁(yè)，編輯于2023年，星期三樹(shù)n個(gè)結(jié)點(diǎn)的有限集合,n>1,T:1.一個(gè)根結(jié)點(diǎn)root2.1245673n=0n=11第四頁(yè)，共二十八頁(yè)，編輯于2023年，星期三abdefgc樹(shù)的術(shù)語(yǔ)結(jié)點(diǎn)=數(shù)據(jù)項(xiàng)+分枝結(jié)點(diǎn)的度葉、分支、子女、雙親、兄弟

祖先、子孫結(jié)點(diǎn)所處層次樹(shù)的高度樹(shù)的度有序樹(shù)、無(wú)序樹(shù)森林abdefgcadg第五頁(yè)，共二十八頁(yè)，編輯于2023年，星期三二叉樹(shù)n個(gè)結(jié)點(diǎn)的集合，T：,n=0T左+T右，n>0T=

(a)空二叉樹(shù)AABABACB(b)根和空的左右子樹(shù)(c)根和左子樹(shù)(d)根和右子樹(shù)(e)根和左右子樹(shù)第六頁(yè)，共二十八頁(yè)，編輯于2023年，星期三二叉樹(shù)的性質(zhì)性質(zhì)1：在二叉樹(shù)的第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)。證畢。第七頁(yè)，共二十八頁(yè)，編輯于2023年，星期三性質(zhì)3：對(duì)任何一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2＋1。性質(zhì)2：深度為k的二叉樹(shù)至多有2k－1個(gè)結(jié)點(diǎn)（k>=1).證明：設(shè)二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)為n1，有：

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

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

n0＝n2＋12453671第八頁(yè)，共二十八頁(yè)，編輯于2023年，星期三滿(mǎn)二叉樹(shù):深度為k且共有2k-1個(gè)結(jié)點(diǎn)12345612345712367(a)完全二叉樹(shù)(b)非完全二叉樹(shù)(c)非完全二叉樹(shù)2453671完全二叉樹(shù)葉結(jié)點(diǎn)出現(xiàn)在最高或次高層對(duì)于任意結(jié)點(diǎn),如果C(Tr)=s,則C(Tl)=s或s+1第九頁(yè)，共二十八頁(yè)，編輯于2023年，星期三性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為123452k-1－1<n<=2k-12k-1<=n<2k第十頁(yè)，共二十八頁(yè)，編輯于2023年，星期三性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(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第十一頁(yè)，共二十八頁(yè)，編輯于2023年，星期三遍歷二叉樹(shù)2453671LDR

DLR——先（根）序遍歷

LDR——中（根）序遍歷LRD——后（根）序遍歷第十二頁(yè)，共二十八頁(yè)，編輯于2023年，星期三二叉樹(shù)表達(dá)式(a+b*(c-d)-e/f)－＋*a/b-dcfe其先序序列為：-+a*b-cd/ef

其中序序列為：a+b*c-d-e/f其后序序列為：abcd-*+ef/-第十三頁(yè)，共二十八頁(yè)，編輯于2023年，星期三鏈?zhǔn)酱鎯?chǔ)A^BC^D^E^F^^G^^H^lchildDatarchild第十四頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

typedefstructBiTNode{

Elemtypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;lchildDatarchild第十五頁(yè)，共二十八頁(yè)，編輯于2023年，星期三BiTreeCreate(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;}ABCDFEGABC##DE#G##F###T^^^^^^^^第十六頁(yè)，共二十八頁(yè)，編輯于2023年，星期三-+a##*b##-c##d##/e##f##－＋*a/b-dcfe第十七頁(yè)，共二十八頁(yè)，編輯于2023年，星期三前序遍歷voidPreorder(BiTreeT){if(T){cout<<T->data;Preorder(T->lchild);Preorder(T->rchild);}}－＋*a/b-dcfe第十八頁(yè)，共二十八頁(yè)，編輯于2023年，星期三葉結(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第十九頁(yè)，共二十八頁(yè)，編輯于2023年，星期三intDepth(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樹(shù)的深度第二十頁(yè)，共二十八頁(yè)，編輯于2023年，星期三線索化二叉樹(shù)ABCDE^^^^^^中序遍歷BDAEC^^第二十一頁(yè)，共二十八頁(yè)，編輯于2023年，星期三lchildltagdatartagrchild0A01B00C11D11E1中序遍歷BDAEC^^第二十二頁(yè)，共二十八頁(yè)，編輯于2023年，星期三樹(shù)的存儲(chǔ)表示firstcdatanextscefdhjabgklim第二十三頁(yè)，共二十八頁(yè)，編輯于2023年，星期三森林轉(zhuǎn)化為二叉樹(shù)cefdhjabgki第二十四頁(yè)，共二十八頁(yè)，編輯于2023年，星期三路徑長(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)度第二十五頁(yè)，共二十八頁(yè)，編輯于2023年，星期三HuffmanTreeT有n個(gè)葉結(jié)點(diǎn)，權(quán)值w0,…wn-1,擴(kuò)充二叉樹(shù)T的帶權(quán)路徑長(zhǎng)度：245724577524WPL最小的二叉樹(shù)第二十六頁(yè)，共二十八頁(yè)，編輯