数据结构递归树.ppt

上传人:王** 文档编号:163037 上传时间:2023-03-02 格式:PPT 页数:27 大小:424KB
下载 相关 举报
数据结构递归树.ppt_第1页
第1页 / 共27页
数据结构递归树.ppt_第2页
第2页 / 共27页
数据结构递归树.ppt_第3页
第3页 / 共27页
数据结构递归树.ppt_第4页
第4页 / 共27页
数据结构递归树.ppt_第5页
第5页 / 共27页
数据结构递归树.ppt_第6页
第6页 / 共27页
数据结构递归树.ppt_第7页
第7页 / 共27页
数据结构递归树.ppt_第8页
第8页 / 共27页
数据结构递归树.ppt_第9页
第9页 / 共27页
数据结构递归树.ppt_第10页
第10页 / 共27页
亲,该文档总共27页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构递归树.ppt》由会员分享,可在线阅读,更多相关《数据结构递归树.ppt(27页珍藏版)》请在优知文库上搜索。

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; 树

2、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,假

3、定命题成立,则第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)非完全二叉树

4、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

5、/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-

6、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

7、); 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森林转化

8、为二叉树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

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!