递归树-课件（PPT-精）.ppt

数据结构递归: typedef struct tNode{ Elemtype data; tNode *next;}tNode,*link;tNode newnode;link list; 递归 部分地包含自身，直接或间接地调用自身 定义递归： 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 树 n个结点的有限集合,n1,T: 1. 一个根结点root 2. 1 2 4 5 6 7 3 n=0 n=1 1 a b d e f g c 树的术语 结点=数据项+分枝 结点的度 叶、分支、子女、双亲、兄弟祖先、子孙 结点所处层次 树的高度 树的度 有序树、无序树 森林 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) 2 4 5 3 6 7 1 当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，则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＋1 2 4 5 3 6 7 1 满二叉树:深度为k且共有2k-1个结点 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 6 7 (a)完全二叉树 (b)非完全二叉树 ( c)非完全二叉树 2 4 5 3 6 7 1 完全二叉树 叶结点出现在最高或次高层 对于任意结点,如果 C(Tr)=s,则C(Tl)=s或s+1 性质4 具有n个结点的完全二叉树深度为 1 2 3 4 5 2k-1－1n=2k-1 2k-1=n2k 性质5： 如果对一棵有n个结点的完全二叉树的结点从高到低从左到右编号,则对任一结点i,有： 1）i＝1，则i无双亲，是根；i1，则双亲【i/2】; 2)2in，则i为叶子；否则，其左孩子是2i; 3）如果2i＋1n，则结点i无右孩子；否则，其右孩子是结点2i＋1。 1 2 3 4 5 6 1 2 3 4 5 2 4 5 3 6 7 1 遍历二叉树 2 4 5 3 6 7 1 L D R DLR——先（根）序遍历 LDR——中（根）序遍历 LRD——后（根）序遍历 二叉树表达式 (a+b*(c-d)-e/f) － ＋ * a / b - d c f e 其先序序列为： -+a*b-cd/ef 其中序序列为： a+b*c-d-e/f 其后序序列为： abcd-*+ef/- 链式存储 A ^ B C ^ D ^ E ^ F ^ ^ G ^ ^ H ^ lchild Data rchild typedef struct BiTNode{ Elemtype data; struct BiTNo