数据结构递归树

数据结构递归树第1页，共28页，2023年，2月20日，星期六部分地包含自身，直接或间接地调用自身定义递归：longFactor(longn){if(n==0)return1;elsereturnn*Factor(n-1);}参数计算返回00！=11

参数计算返回11*Factor(0)

参数计算返回22*Factor(1)

参数计算返回33*Factor(2)

主程序main()32101266第2页，共28页，2023年，2月20日，星期六数据结构递归:typedefstructtNode{

Elemtypedata;

tNode*next;

}tNode,*link;

tNodenewnode;

linklist;^^^第3页，共28页，2023年，2月20日，星期六树n个结点的有限集合,n>1,T:1.一个根结点root2.1245673n=0n=11第4页，共28页，2023年，2月20日，星期六abdefgc树的术语结点=数据项+分枝结点的度叶、分支、子女、双亲、兄弟

祖先、子孙结点所处层次树的高度树的度有序树、无序树森林abdefgcadg第5页，共28页，2023年，2月20日，星期六二叉树n个结点的集合，T：,n=0T左+T右，n>0T=

(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树第6页，共28页，2023年，2月20日，星期六二叉树的性质性质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个结点。证毕。第7页，共28页，2023年，2月20日，星期六性质3：对任何一棵二叉树，如果其叶结点数n0，度为2的结点数为n2，则n0＝n2＋1。性质2：深度为k的二叉树至多有2k－1个结点（k>=1).证明：设二叉树中度为1的结点数为n1，有：

N＝n0＋n1＋n2(1)设B为二叉树中的分支总数，则有B=N-1，同时B=n1+2n2,于是有

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

n0＝n2＋12453671第8页，共28页，2023年，2月20日，星期六满二叉树:深度为k且共有2k-1个结点12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树2453671完全二叉树叶结点出现在最高或次高层对于任意结点,如果C(Tr)=s,则C(Tl)=s或s+1第9页，共28页，2023年，2月20日，星期六性质4具有n个结点的完全二叉树深度为123452k-1－1<n<=2k-12k-1<=n<2k第10页，共28页，2023年，2月20日，星期六性质5：如果对一棵有n个结点的完全二叉树的结点从高到低从左到右编号,则对任一结点i,有：1）i＝1，则i无双亲，是根；i>1，则双亲【i/2】;2)2i>n，则i为叶子；否则，其左孩子是2i;3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。123456123452453671第11页，共28页，2023年，2月20日，星期六遍历二叉树2453671LDR

DLR——先（根）序遍历

LDR——中（根）序遍历LRD——后（根）序遍历第12页，共28页，2023年，2月20日，星期六二叉树表达式(a+b*(c-d)-e/f)－＋*a/b-dcfe其先序序列为：-+a*b-cd/ef

其中序序列为：a+b*c-d-e/f其后序序列为：abcd-*+ef/-第13页，共28页，2023年，2月20日，星期六链式存储A^BC^D^E^F^^G^^H^lchildDatarchild第14页，共28页，2023年，2月20日，星期六

typedefstructBiTNode{

Elemtypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;lchildDatarchild第15页，共28页，2023年，2月20日，星期六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^^^^^^^^第16页，共28页，2023年，2月20日，星期六-+a##*b##-c##d##/e##f##－＋*a/b-dcfe第17页，共28页，2023年，2月20日，星期六前序遍历voidPreorder(BiTreeT){if(T){cout<<T->data;Preorder(T->lchild);Preorder(T->rchild);}}－＋*a/b-dcfe第18页，共28页，2023年，2月20日，星期六叶结点个数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第19页，共28页，2023年，2月20日，星期六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树的深度第20页，共28页，2023年，2月20日，星期六线索化二叉树ABCDE^^^^^^中序遍历BDAEC^^第21页，共28页，2023年，2月20日，星期六lchildltagdatartagrchild0A01B00C11D11E1中序遍历BDAEC^^第22页，共28页，2023年，2月20日，星期六树的存储表示firstcdatanextscefdhjabgklim第23页，共28页，2023年，2月20日，星期六森林转化为二叉树cefdhjabgki第24页，共28页，2023年，2月20日，星期六路径长度：结点间的分支数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层，最小路径长度第25页，共28页，2023年，2月20日，星期六HuffmanTreeT有n个叶结点，权值w0,…wn-1,扩充二叉树T的带权路径长度：245724577524WPL最小的二叉树第26页，共28页，2023年