• / 146
  • 下载费用:10 金币  

《数据结构》(C语言版)第六章_树和二叉树.ppt

关 键 词:
《数据结构》(C语言版)第六章_树和二叉树.ppt
资源描述:
第六章 树和二叉树,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 赫夫曼树及其应用,,学习提要: 掌握二叉树的性质,了解相应的证明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范围。 3. 掌握各种遍历策略的递归算法,灵活运用遍历算法实现二叉树的其它操作。 4. 理解二叉树线索化的实质,熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 5. 熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。,6. 了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。重难点内容:二叉树的性质及其证明、二叉树的遍 历、二叉树的线索化、树和森林与二叉树 的转换、哈夫曼树的遍历和哈夫曼编码。,,§6.1 树的定义和基本术语,6.1.2 基本术语,6.1.1 树的类型定义,6.1.1 树的类型定义,树的抽象数据类型定义:,ADT Tree{数据对象 D: D是具有相同特性的数据元素的集合。数据关系 R: 若D为空集,则称为空树。否则:(1) 在D中存在唯一的称为根(root)的结点;(2) 当n1时,其余结点可分为m (m0)个互不相交的有限集T1, T2, …, Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根的子树(SubTree)。基本操作P: } ADT Tree,,……,,,,根,子树,,基本操作:,查 找 类,插 入 类,删 除 类,,,,,Root(T) // 求树的根结点,查找类:,Value(T, cur_e) // 求当前结点的元素值,Parent(T, cur_e) // 求当前结点的双亲结点,LeftChild(T, cur_e) // 求当前结点的最左孩子,RightSibling(T, cur_e) // 求当前结点的右兄弟,TreeEmpty(T) // 判定树是否为空树,TreeDepth(T) // 求树的深度,TraverseTree( T, Visit() ) // 遍历,,InitTree(&T) // 初始化置空树,插入类:,CreateTree(&T, definition) // 按定义构造树,Assign(T, cur_e, value) // 给当前结点赋值,InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树,,ClearTree(&T) // 将树清空,删除类:,DestroyTree(&T) // 销毁树的结构,DeleteChild(&T, &p, i) // 删除结点p的第i 棵子树,,6.1.2 基本术语,结点(node):数据元素+若干指向子树的分支。 结点的度(degree):分支个数。 树的度:树中所有结点的度的最大值。 叶子结点:度为0的结点,也称终端结点。 分支结点:度大于0的结点,也称非终端结点。,(从根到结点的)路径:,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度:,由从根到该结点所经分支和结点构成。,,假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1。,树中叶子结点所在的最大层次。,任何一棵非空树是一个二元组Tree = (root,F) 其中:root 被称为根结点F 被称为子树森林,森林:,是m(m≥0)棵互 不相交的树的集合。,A,root,,B,C,D,E,F,G,H,I,J,M,K,L,,,,,,,,,,F,,,,,(1) 有确定的根; (2) 树根和子树根之间为有向关系。,有向树:,有序树:,子树之间存在确定的次序关系。,无序树:,子树之间不存在确定的次序关系。,,,线性结构,树形结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素 (一个前驱、一个后继),其它数据元素 (一个前驱、多个后继),,,,§6.2 二叉树,6.2.2 二叉树的性质,6.2.1 二叉树的类型定义,6.2.3 二叉树的存储结构,二叉树或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,,,,,,,,,,,根结点,左子树,右子树,6.2.1 二叉树的类型定义,二叉树的五种基本形态:,,,N,,,,,N,N,N,L,R,R,L,二叉树和树是两种不同的树型结构,二叉树不等同于度为2的有序树。 如果根结点只有一棵子树,那么对树而言,它就是一个“独生子“,无次序可分,但对二叉树而言,必须明确区分它是根的左子树还是根的右子树,两者将构成不同的二叉树。,二叉树的主要基本操作:,查 找 类,插 入 类,删 除 类,,Root(T); Value(T, e); Parent(T,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:《数据结构》(C语言版)第六章_树和二叉树.ppt
链接地址:https://www.weizhuannet.com/p-10026160.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开