数据结构递归树.ppt
部分地包含自身，直接或间接地调用自身定义递归：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个结点的有限集合,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-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完全二叉树 叶结点出现在最高或次高层对于任意结点,如果 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/-链式存储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; ABCDFEGABC#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) 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:111245761118011100
