数据结构递归树.ppt

《数据结构递归树.ppt》由会员分享，可在线阅读，更多相关《数据结构递归树.ppt（27页珍藏版）》请在课桌文档上搜索。

1、部分地包含自身，直接或间接地调用自身,定义递归：,long Factor(long n)if(n=0)return 1;else return n*Factor(n-1);,参数 计算 返回 0 0！=1 1,参数 计算 返回 1 1*Factor(0),参数 计算 返回 2 2*Factor(1),参数 计算 返回 3 3*Factor(2),主程序main(),3,2,1,0,1,2,6,6,数据结构递归:,typedef struct tNode Elemtype data;tNode*next;tNode,*link;tNode newnode;link list;,树,n个结点的有限

2、集合,n1,T:,1.一个根结点root,2.,n=0,n=1,1,树的术语,结点=数据项+分枝,结点的度,叶、分支、子女、双亲、兄弟祖先、子孙,结点所处层次,树的高度,树的度,有序树、无序树,森林,a,b,d,e,f,g,c,a,d,g,二叉树,n个结点的集合，T：,n=0,T左+T右，n0,T=,(a)空二叉树,A,A,B,A,B,A,C,B,(b)根和空的左右子树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,二叉树的性质,性质1：在二叉树的第i层上至多有2i-1个结点(i=1),当i=1时，只有一个根结点，2i-1=20=1,命题成立。对于j=i-1,假定命题成立，则第j层上

3、至多有2j-1个结点，故第j+1层上最多有2j-1*2即2j个结点，即第i层上最多有2i-1个结点。证毕。,性质3：对任何一棵二叉树，如果其叶结点数n0，度为2的结点数为n2，则n0n21。,性质2：深度为k的二叉树至多有2k1个结点（k=1).,证明：设二叉树中度为1的结点数为n1，有：Nn0n1n2(1)设B为二叉树中的分支总数，则有B=N-1，同时B=n1+2n2,于是有 N=n1+2n2-1(2)故 n0n21,满二叉树:深度为k且共有2k-1个结点,1,2,3,4,5,6,1,2,3,4,5,7,1,2,3,6,7,(a)完全二叉树,(b)非完全二叉树,(c)非完全二叉树,完全二叉树

4、,叶结点出现在最高或次高层,对于任意结点,如果,C(Tr)=s,则C(Tl)=s或s+1,性质4 具有n个结点的完全二叉树深度为,2k-11n=2k-1,2k-1=n2k,性质5：如果对一棵有n个结点的完全二叉树的结点从高到低从左到右编号,则对任一结点i,有：1）i1，则i无双亲，是根；i1，则双亲【i/2】;2)2in，则i为叶子；否则，其左孩子是2i;3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,遍历二叉树,DLR先（根）序遍历 LDR中（根）序遍历 LRD后（根）序遍历,二叉树表达式(a+b*(c-d)-e/f),其先序序列为：-+a*b-cd/ef 其中序序列为：a

5、+b*c-d-e/f其后序序列为：abcd-*+ef/-,链式存储,typedef struct BiTNode Elemtype data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,BiTree Create(BiTree T)char ch;cinch;if(ch=#)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)coutdata=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild);return T;,ABC#DE#G#F#,

6、T,-+a#*b#-c#d#/e#f#,前序遍历,void Preorder(BiTree T)if(T)coutdata;Preorder(T-lchild);Preorder(T-rchild);,叶结点个数,int Sumleaf(BiTree T)int sum=0,m,n;if(T)if(!T-lchild),int Depth(BiTree T)int dep=0,depl,depr;if(!T)dep=0;else depl=Depth(T-lchild);depr=Depth(T-rchild);dep=1+(depldepr?depl:depr);return dep;,树的

7、深度,线索化二叉树,中序遍历BDAEC,中序遍历BDAEC,树的存储表示,c,e,f,d,h,j,a,b,g,k,l,i,m,森林转化为二叉树,c,e,f,d,h,j,a,b,g,k,i,路径长度：结点间的分支数,2,4,5,3,6,7,1,8,2,4,1,3,6,8,5,7,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4.,0,1,1,2,2,2,3,3,n个结点,高为k,从根到k-1层最多有2k-1-1个点，其余分布在第k层，最小路径长度,Huffman Tree,T有n个叶结点，权值w0,wn-1,扩充二叉树,T的带权路径长度：,2,4,5,7,2,4,5,7,7,5,2,4,WPL最小的二叉树,构造Huffman Tree,2,4,5,7,6,11,18,CAST CAST SAT AT A TASA,C,A,S,T:2,7,4,5,0,1,1,1,0,0,A:0,T:10,C:110,S:111,2,4,5,7,6,11,18,0,1,1,1,0,0,