电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

数据结构第八次课-树BVIP免费

数据结构第八次课-树B_第1页
1/22
数据结构第八次课-树B_第2页
2/22
数据结构第八次课-树B_第3页
3/22
调课通知下周(第5周)星期一1~2节的数据结构课调到:下周(第5周)星期四5~6节教室:L24122.2.二叉树的性质二叉树的性质(3+2)(3+2)性质1:在二叉树的第i层上至多有22i-1i-1个结点(i>0)。性质2:深度为k的二叉树至多有22kk-1-1个结点(k>0)。性质3:对于任何一棵二叉树,若2度的结点数有n2个,则叶子数n0必定为n2+1(即n0=n2+1)上堂课内容回顾1.1.树的基本知识树的基本知识树的定义、若干术语、逻辑结构、存储结构、基本运算对于两种特殊形式的二叉树(满二叉树和完全二叉树),还特别具备以下2个性质:性质4:具有n个结点的完全二叉树的深度必为log2n+1性质5:对完全二叉树,若从上至下、从左至右编号,则编号为i的结点,其左孩子编号必为2i,其右孩子编号为2i+1;其双亲的编号必为i/2(i=1时为根,除外)。ABCDEGFHIKJMLNO152346789101112131415ACBEDFGHIJ12435768910上堂课例题讨论问:设一棵完全二叉树具有1000个结点,则它有500个叶子结点,有499个度为2的结点,有1个结点只有非空左子树,有0个结点只有非空右子树。法1:先求全部叶子数。n0=489(末层)+11(k-1层)=500个;法2:先求2度结点数。n2=255(k-2层)+244(k-1层)=499个;这两种方法的缺点:都要先计算树的深度k=log2n+1=10;法3:无需求树深k,便可快捷求出完全二叉树的叶子数:完全二叉树的叶子数:nn00==n/2n/2////取大于n/2的最小整数值可由二叉树性质5轻松证明!(编号为i的结点,其孩子编号必为2i和2i+1)①②④⑧⑤⑨③??⑦……nn已知最后一个结点编号为n,则其双亲n/2肯定是最后一个非叶子结点。其编号之后的全部结点都是叶子了!故,n0=n-n/2=n/2n/2问:设一棵完全二叉树具有n个结点,第一个叶子节点的编号是?第i个呢?4.二叉树的存储结构一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号,用一组连续的存储单元存储。AABBCCDDEEFFGGHHII[1][2][3][4][5][6][7][8][9]AABBCCGGEEIIDDHHFF问:顺序存储后能否复原成唯一对应的二叉树形状?答:若是完全/满二叉树则可以做到唯一复原。而且有规律:下标值为i的双亲,其左孩子的下标值必为2i,其右孩子的下标值必为2i+1(即性质5)例如,对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。T[0]一般不用讨论:不是完全二叉树怎么办?答:一律转为完全二叉树!方法很简单,将各层空缺处统统补上“虚结点”,其内容为空。AABB^^CC^^^^^^DD^^……EE[1][2][3][4][5][6][7][8][9].[16]ABECD缺点:①浪费空间;②插入、删除不便二、链式存储结构(1)用二叉链表即可方便表示。datadataleft_childleft_childright_childright_childdatadataleft_childleft_childright_childright_child二叉树结点数据类型定义:P106代码6-1一般从根结点开始存储。(相应地,访问树中结点时也只能从根开始)注:如果需要倒查某结点的双亲,可以再增加一个双亲域(直接前趋)指针,将二叉链表变成三叉链表。例1:ABECD^^AABB^^DD^^CC^^^^EE^^ABECD有n个结点的树采用二叉链表存储有多少空指针域?指针域有2n个,有效的为n-1个,剩余都为空指针。A∧B∧∧∧∧∧∧∧CDEFG∧∧∧∧∧∧ADEFBC∧∧G例2:ABDCEFG(2)树的三叉链表表示lchilddatarchildparentA∧∧BD∧∧E∧C∧F∧∧G∧ABDCEFG第6章树和二叉树(Tree&BinaryTree)6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用(今日授课内容是本章及本课程的重点)(今日授课内容是本章及本课程的重点)6.3遍历二叉树和线索二叉树一、遍历二叉树(TraversingBinaryTree)遍历定义——指按某条搜索路线遍访每个结点且不重复(又称周游)。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。遍历方法——牢记一种约定,对每个结点的查看都是“先左后右”。遍历规则———二叉树由根、左子树、右子树构成,定义为D、L、RD、L、R的组合定义了六种可能的遍历方案:LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右,则有三种实现方案:DLRLDRLRD先(根)序遍历中(根)序遍历后(根)序遍历注:“先、中、后”的意思是指访问...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

数据结构第八次课-树B

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部