数据结构递归树课件.ppt

1、部分地包含自身，直接或间接地调用自身定义递归：0 )!1(0 1!nnnnnlong 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()32101266数据结构递归:typedef struct tNode Elemtype data;tNode*next;tNode,*link;tNode newnode;link list;树n个结点的有限集合,

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

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

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

5、式存储ABCD E F GH lchildDatarchildtypedef struct BiTNode Elemtype data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;lchildDatarchildBiTree 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;A

6、BCDFEGABC#DE#G#F#T-+a#*b#-c#d#/e#f#*a/b-dcfe前序遍历void Preorder(BiTree T)if(T)coutdata;Preorder(T-lchild);Preorder(T-rchild);*a/b-dcfe叶结点个数int Sumleaf(BiTree T)int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)sum+;m=Sumleaf(T-lchild);sum+=m;n=Sumleaf(T-rchild);sum+=n;return sum;*a/b-dcfeint Depth(BiTree T)

7、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;*a/b-dcfe树的深度线索化二叉树ABCDE中序遍历BDAEClchildltagdatartagrchild0A 01 B 00C11D 11 E1中序遍历BDAEC树的存储表示firstcdatanextscefdhjabgklim森林转化为二叉树cefdhjabgki路径长度：结点间的分支数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层，最小路径长度Huffman TreeT有n个叶结点，权值w0,wn-1,扩充二叉树T的带权路径长度：10niiilwWPL245724577524WPL最小的二叉树构造Huffman Tree245761118CAST CAST SAT AT A TASAC,A,S,T:2,7,4,5245761118011100A:0,T:10,C:110,S:111精品课件精品课件！精品课件精品课件！245761118011100