數(shù)據(jù)結構遞歸樹

數(shù)據(jù)結構遞歸樹第一頁，共二十八頁，2022年，8月28日部分地包含自身，直接或間接地調用自身定義遞歸：longFactor(longn){if(n==0)return1;elsereturnn*Factor(n-1);}參數(shù)計算返回00！=11

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

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

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

主程序main()32101266第二頁，共二十八頁，2022年，8月28日數(shù)據(jù)結構遞歸:typedefstructtNode{

Elemtypedata;

tNode*next;

}tNode,*link;

tNodenewnode;

linklist;^^^第三頁，共二十八頁，2022年，8月28日樹n個結點的有限集合,n>1,T:1.一個根結點root2.1245673n=0n=11第四頁，共二十八頁，2022年，8月28日abdefgc樹的術語結點=數(shù)據(jù)項+分枝結點的度葉、分支、子女、雙親、兄弟

祖先、子孫結點所處層次樹的高度樹的度有序樹、無序樹森林abdefgcadg第五頁，共二十八頁，2022年，8月28日二叉樹n個結點的集合，T：,n=0T左+T右，n>0T=

(a)空二叉樹AABABACB(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹第六頁，共二十八頁，2022年，8月28日二叉樹的性質性質1：在二叉樹的第i層上至多有2i-1個結點(i>=1)2453671當i=1時，只有一個根結點，2i-1=20=1,命題成立。對于j=i-1,假定命題成立，則第j層上至多有2j-1個結點，故第j+1層上最多有2j-1*2即2j個結點，即第i層上最多有2i-1個結點。證畢。第七頁，共二十八頁，2022年，8月28日性質3：對任何一棵二叉樹，如果其葉結點數(shù)n0，度為2的結點數(shù)為n2，則n0＝n2＋1。性質2：深度為k的二叉樹至多有2k－1個結點（k>=1).證明：設二叉樹中度為1的結點數(shù)為n1，有：

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

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

n0＝n2＋12453671第八頁，共二十八頁，2022年，8月28日滿二叉樹:深度為k且共有2k-1個結點12345612345712367(a)完全二叉樹(b)非完全二叉樹(c)非完全二叉樹2453671完全二叉樹葉結點出現(xiàn)在最高或次高層對于任意結點,如果C(Tr)=s,則C(Tl)=s或s+1第九頁，共二十八頁，2022年，8月28日性質4具有n個結點的完全二叉樹深度為123452k-1－1<n<=2k-12k-1<=n<2k第十頁，共二十八頁，2022年，8月28日性質5：如果對一棵有n個結點的完全二叉樹的結點從高到低從左到右編號,則對任一結點i,有：1）i＝1，則i無雙親，是根；i>1，則雙親【i/2】;2)2i>n，則i為葉子；否則，其左孩子是2i;3）如果2i＋1>n，則結點i無右孩子；否則，其右孩子是結點2i＋1。123456123452453671第十一頁，共二十八頁，2022年，8月28日遍歷二叉樹2453671LDR

DLR——先（根）序遍歷

LDR——中（根）序遍歷LRD——后（根）序遍歷第十二頁，共二十八頁，2022年，8月28日二叉樹表達式(a+b*(c-d)-e/f)－＋*a/b-dcfe其先序序列為：-+a*b-cd/ef

其中序序列為：a+b*c-d-e/f其后序序列為：abcd-*+ef/-第十三頁，共二十八頁，2022年，8月28日鏈式存儲A^BC^D^E^F^^G^^H^lchildDatarchild第十四頁，共二十八頁，2022年，8月28日

typedefstructBiTNode{

Elemtypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;lchildDatarchild第十五頁，共二十八頁，2022年，8月28日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^^^^^^^^第十六頁，共二十八頁，2022年，8月28日-+a##*b##-c##d##/e##f##－＋*a/b-dcfe第十七頁，共二十八頁，2022年，8月28日前序遍歷voidPreorder(BiTreeT){if(T){cout<<T->data;Preorder(T->lchild);Preorder(T->rchild);}}－＋*a/b-dcfe第十八頁，共二十八頁，2022年，8月28日葉結點個數(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第十九頁，共二十八頁，2022年，8月28日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樹的深度第二十頁，共二十八頁，2022年，8月28日線索化二叉樹ABCDE^^^^^^中序遍歷BDAEC^^第二十一頁，共二十八頁，2022年，8月28日lchildltagdatartagrchild0A01B00C11D11E1中序遍歷BDAEC^^第二十二頁，共二十八頁，2022年，8月28日樹的存儲表示firstcdatanextscefdhjabgklim第二十三頁，共二十八頁，2022年，8月28日森林轉化為二叉樹cefdhjabgki第二十四頁，共二十八頁，2022年，8月28日路徑長度：結點間的分支數(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個結點,高為k,從根到k-1層最多有2k-1-1個點，其余分布在第k層，最小路徑長度第二十五頁，共二十八頁，2022年，8月28日HuffmanTreeT有n個葉結點，權值w0,…wn-1,擴充二叉樹T的帶權路徑長度：245724577524WPL最小的二叉樹第二十六頁，共二十八頁，2