计算机软件技术基础课件-第2章 常用数据结构及其运算2(非线性)

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

第二章 常用的数据结构及其运算2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8

概述 线性表 栈与队列 数组 树与二叉树 图 查找 排序

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5 树与二叉树数据结构： 线性结构：……(线性表、栈、队列等等。) 线性结构： 队列等等。) 线性结构 (线性表、 非线性结构： 非线性结构：至少存在一个数据元素有不止一个 非线性结构 直接前驱或直接后继( 直接前驱或直接后继(树、图)。

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5树与二叉树 2.5树与二叉树

一、树的定义基本术语个数据元素组成的有限集合( 个数据元素组成的有限集合 记为T 树是由 n(n>=0)个数据元素组成的有限集合(记为 ),对于 任意一棵树T: 任意一棵树 ： (1) 存在唯一一个称为根的数据元素； ) 存在唯一一个称为根的数据元素； 时其它数据元素可分为m(m>0)个互不相交的有 (2) 当 n>1时其它数据元素可分为 ) > 时其它数据元素可分为 个互不相交的有 限集合 T1,T2,…,Tm,而其中每个集合Ti(i=1,2,…,m) , 而其中每个集合 ， , , ) 本身又是一棵树，并称T 是根的子树 子树。 本身又是一棵树，并称 i是根的子树。

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5树与二叉树 2.5树与二叉树

一、树的定义基本术语 树的结点 树的结点(node) :树中的数据元素和指 树的结点 向其子树的分支。 向其子树的分支。 结点的度 结点的度(degree):一个结点的子树的个 ： 结点的度 数称为该结点的度，度为0 的结点称为叶 数称为该结点的度，度为 的结点称为叶 结点 树的度：树的所有结点中最大的度称为 树的度： 树的度 树的度 。 结点的层次 结点的层次(level):根结点为第一层，其他任何结点的层 结点的层次 ：根结点为第一层， 数等于它的父结点的层数加1。 数等于它的父结点的层数加 。 树的深度 depth ) :树的所有结点中最大的层次称为树的 树的深度( 树的深度 深度或高度。 深度或高度。 森林 森林(Forest ) :m (m≥0)棵互不相交的树的集合。 森林 )棵互不相交的树的集合。

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5树与二叉树 2.5树与二叉树

二、二叉树及其性质 1、二叉树的定义 、二叉树：是结点数为 或每个结点最多只有左右两棵 二叉树：是结点数为0或每个结点最多只有左右两棵 子树的树。二叉树是一种特殊的树，它的特点是： 子树的树。二叉树是一种特殊的树，它的特点是： 每个结点最多只有两棵子树，即不存在度大于2的 每个结点最多只有两棵子树，即不存在度大于 的 每个结点最多只有两棵子树 结点。 结点。 是有序树，子树有左右之分，不能颠倒。 是有序树，子树有左右之分，不能颠倒。 是有序树B A

思考：二叉树和度为2的树有何区别？ 思考： 的树有何

区别？

C E

D F

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5树与二叉树 2.5树与二叉树

二、二叉树及其性质 2、二叉树的基本性质 、层上最多有2 【性质1】第i层上最多有 i-1(i>=1)个结点 性质 】 层上最多有 个结点 证明： 证明： 当i=1,即根结点，结点数为 1-1=1,成立； 当 ，即根结点，结点数为2 ,成立； 假设第i-1层上的结点数最多有 假设第 层上的结点数最多有2(i-1)-1=2i-2个，则： 层上的结点数最多有 由于二叉树中每一个结点度数最大为 ，故第 层上 由于二叉树中每一个结点度数最大为2,故第i层上 由于二叉树中每一个结点度数最大为 结点数至多为i-1层上结点数的 层上结点数的2倍 结点数至多为 层上结点数的 倍，即2×2i-2=2i-1。 × 由归纳法，性质得证。 由归纳法，性质得证。

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5树与二叉树 2.5树与二叉树

二、二叉树及其性质的二叉树最多有2 个节点 【性质2】深度为 的二叉树最多有 h-1个节点 性质 】深度为h的二叉树最多有 证明： 证明： 利用性质(1)的结论，在深度为 的二叉数中至多含有的 利用性质 的结论，在深度为h的二叉数中至多含有的 的结论 结点数： 结点数：

∑ (i层上结点最大数)=∑ 2i =1 i =1

h

h

i 1

= 2 1h

计算机软件技术基础课件第2章-常用数据结构及其运算2(非线性结构)适用于沈被娜主编教材《软件技术基础》第二版,清华大学出版社

2.5树与二叉树 2.5树与二叉树

二、二叉树及其性质【性质3】二叉树中，若有 0个叶子结点， n2个度为 的结 性质 】二叉树中 …… 此处隐藏：2829字，全部文档内容请下载后查看。喜欢就下载吧 ……