第6章二叉树和树1.ppt
《第6章二叉树和树1.ppt》由会员分享,可在线阅读,更多相关《第6章二叉树和树1.ppt(26页珍藏版)》请在三一文库上搜索。
1、1,第6章 二叉树和树1,前面的章节主要讨论的是线性结构,二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。 二叉树及树的遍历技术是本章各种算法的核心,而且大多是以递归的形式表现的,阅读和编写递归算法是学习本章的难点。 讲授本章课程大约需8课时。,2,树结构的特点及基本术语 6.1 二叉树,3,树结构的特点及基本术语,4,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),对比树型结构和线性结构的结构特点,5,结点:数据元素+若干指向
2、子树的分支,结点的度:分支的个数,树的度:树中所有结点的度的最大值,叶子结点:度为零的结点,分支结点:度大于零的结点,基本术语,6,(从根到结点的)路径:,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,由从根到该结点所经分支和结点构成,结点的层次:假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1,树的深度:树中叶子结点所在的最大层次,7,6.1 二叉树,一、二叉树的定义和基本术语 二、二叉树的几个基本性质 三、二叉树的存储结构,8,一、二叉树的定义和基本术语,9,二叉树的定义 二叉树是n(n0)个元素的有限集,它或为空树,或是由一个根结点加上两棵分别称为左子树和右子树
3、的、互不交的二叉树组成。,根结点,左子树,右子树,B,10,二叉树可以表现出五种基本形态:,11,二叉树的基本操作:,查 找 类 的 操 作,插 入 类 的 操 作,删 除 类 的 操 作,12,Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T); InOrderTraverse(T); PostOrderTraverse(T
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉
链接地址:https://www.31doc.com/p-2567009.html