数据结构树与二叉树的ppt.ppt

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：1.60M 资料格式：ppt 举报版权申诉

bb890312-1966733-4744302543431030677.ppt.pdf-第1页.png

第1页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第2页.png

第2页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第3页.png

第3页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第4页.png

第4页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第5页.png

第5页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第6页.png

第6页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第7页.png

第7页 / 共141页

bb890312-1966733-4744302543431030677.ppt.pdf-第8页.png

第8页 / 共141页

文本预览

第六章树和二叉树一、教学内容 1、树和森林的概念（树的定义、树的术语、性质及运算）； 2、二叉树的定义、性质及运算； 3、二叉树的存储结构（顺序、链式表示）； 4、遍历二叉树 5、树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林 6、哈夫曼树、哈夫曼编码。二、教学要求： 1、了解树和森林的概念。包括树的定义、树的术语和性质； 2、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围； 3、熟练掌握二叉树的遍历方法及遍历算法； 4、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法 5、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。

第六章树和二叉树树是一类重要的非线性数据结构，是以分支关系定义的层次结构 6.1 树的定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点：树中至少有一个结点——根树中各子树是互不相交的集合

只有根结点的树 A 有子树的树 B E F K L A C G H M 根 D I J 子树

树的形式定义树是n个数据元素的有限集(记为T)，对任意一棵树T有： ⒈ 存在唯一一个称为根的数据元素； ⒉ 当n＞1时，其它数据元素可分为m(m＞0) 个互不相交的有限集T1,T2,…,Tm，其中每个集合Ti(i=1,2,…,m)本身又是一棵树，并称树 Ti是根的子树.

性质：树是包含了n个结点的有穷集合V且在V上定义了一个关系E ，显然有 ①有仅有一个结点v0∈ V,对关系来说没有前驱，则称之为树根。 ②除结点v0外， V中每个结点都有且仅有一个前驱。 ③除结点v0外， V中任何一个结点v∈ V都存在这样一个序列v0 v1，… vk, vk= v, v0是树根，有序对（ki-1,ki） ∈ E,这样结点序列称之为路径。树是一个连通的不含回路的图

树还有这样的性质： n 树中每一个结点有唯一的一条通路 n 在树中，顶点数比边数多一。

基本术语（1）（1）树的结点。树的结点包含一个数据元素及若干指向其子树的分支。（2）结点的度（Degree）。结点所拥有的子树数称为结点的度。（3）叶子（Leaf）。度为0的结点称为叶子，或者称为终端结点。（4）分支结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。（5）树的度。树中各结点度的最大值称为该树的度。（6）边（edge）：两个结点的有序对，称之联接这两个结点的边。（7）孩子（Child）、双亲（Parent）、兄弟（Sibling）。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（8）祖先、子孙。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。

基本术语（2）（9）结点的层数（Level）。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。（10）堂兄弟。其双亲在同一层的结点互为堂兄弟。（11）树的深度（Depth）。树中所有结点的最大层数称为树的深度，也即高度。（12）有序树和无序树。如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。（13）森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。

分享到：

赞收藏

资料库

数据结构树与二叉树的ppt.ppt

相关推荐

开发技术

热门标签

最新资料