[理学]第6章 树与二叉树.ppt

  1. 1、本文档共156页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[理学]第6章 树与二叉树

第6章 树和二叉树 6.1 树的定义和基本术语 1. 树的定义 树的抽象数据类型定义 树的表示法有几种: 广义表表示法 左孩子-右兄弟表示法 2. 若干术语 2. 若干术语(续) 3. 树的逻辑结构 (特点): 一对多(1:n),有多个直接后继(如家谱树、目录树等等),但只有一个根结点,且子树之间互不相交。 讨论3:树的链式存储方案应该怎样制定? 可规定为:从上至下、从左至右将树的结点依次存入内存。 重大缺陷:复原困难(不能唯一复原就没有实用价值)。 5. 树的运算 要明确: 1. 普通树(即多叉树)若不转化为二叉树,则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等,但这些操作必须建立在对树结点能够“遍历”的基础上! (遍历——指每个结点都被访问且仅访问一次,不遗漏不重复)。 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树? 二叉树的结构最简单,规律性最强; 可以证明,所有树都能转换为唯一的一棵二叉树与其对应,不失一般性。 6.2.1 二叉树的定义 二叉树的抽象数据类型定义(见教材P121-122) 6.2.2 二叉树的性质 (3+2) 讨论3:二叉树的叶子数n0和度为2的结点数n2之间有关系吗? 满二叉树:一棵深度为k 且有2k -1个结点的二叉树。 (特点:每层都“充满”了结点) 课堂讨论: 课堂讨论: 6.2.3 二叉树的存储结构 讨论:不是完全二叉树怎么办? 二、链式存储结构 用二叉链表即可方便表示。 6.3 遍历二叉树和线索二叉树 例1: 例2:用二叉树表示算术表达式 二、遍历的递归算法实现:用递归形式格外简单! 先序遍历算法 DLR( tree *root ) { if (root !=NULL) { //非空二叉树 printf(“%d”,root-data); //访问D DLR(root-lchild); //递归遍历左子树 DLR(root-rchild); //递归遍历右子树 } return(0); } 三、对遍历的分析: 五、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 5、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 讨论: 6.3.2 线索二叉树 线索二叉树的相关概念? 线索链表的遍历算法 如何建立线索链表? 规 定: 例:画出以下二叉树对应的中序线索二叉树。 二叉树小结 6.4 树和森林 6.4.1 树的存储结构 例1: 双亲表示法 2、用孩子表示法来存储 3、用孩子兄弟表示法来存储 例如: 6.4.2 树和森林与二叉树的转换 树与二叉树转换 树转二叉树举例: 讨论2:二叉树怎样还原为树? 森林转换成二叉树(法一) 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构 森林转二叉树举例:(法二) 讨论4:二叉树如何还原为森林? 6.4.3 树和森林的遍历 森林的遍历 6.6 Huffman树及其应用 2、Huffman树简介: 4、如何构造Huffman树? 步骤如下: 构造Huffman树的步骤: 操作要点2:按左0右1对Huffman树的所有分支编号! 例2:假设用于通信的电文仅由8个字母{ a,b,c,d,e,f,g,h } 构成,它们在电文中出现的概率如下表所示,试为这8个字母设计哈夫曼编码。如果用0~7的二进制编码方案又如何? 赫夫曼编码举例 typedef struct { char ch; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*Huffmantree; Huffmantree HT; HT = new HTNode[2*n]; //赫夫曼树的存储结构 typedef char **hufmanCode ; 赫夫曼编码举例 赫夫曼编码举例 赫夫曼编码的求解算法 typedef struct { char ch; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*Huffmantree; Huffmantree HT; HT = new HTNode[2*n];//赫夫曼树的存储结构 typedef char **hufmanCode ; 赫夫曼编码的求解算法 void HuffmanCoding(Huff

文档评论(0)

skvdnd51 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档