计算机软件技术基础课件第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个度为 的结 性质 】二叉树中，若有n 个叶子结点， 个度为2的结 则必有n 点，则必有 0=n2+1 证明： 为度为1的结点数 则总结点数n为 的结点数， 证明：设n1为度为 的结点数，则总结点数 为：

n=n0+n1+n2在二叉树中除根结点外，其他n-1个结点都是度为 个结点都是度为1 在二叉树中除根结点外，其他 个结点都是度为 或度为 2 的结点的孩子，度为1的结点有一个孩子， 的结点的孩子，度为 的结点有一个孩子， 的结点有一个孩子 个孩子， 度为 2 的结点有 2个孩子，因而又有： 个孩子 因而又有：

n-1 =n1+2×n2 ×以上两式联立.即得 以上两式联立 即得

n0=n2+1

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

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

二、二叉树及其性质 3、几种特殊形式的二叉树 、满二叉树： (1)满二叉树：深度为 结点个数为 k-1 的二叉树。 满二叉树 深度为k, 结点个数为2 的二叉树。 每一层的结点数都达到最大值 每一层的结点数都达到最大值. 没有度为 的结点(只有度为 和2的结点),叶子都 没有度为1的结点 只有度为0和 的结点),叶子都 的结点), 没有度为 的结点( 分布在最后一层上。 分布在最后一层上。 编号： 自上而下，自左至右。 编号： 自上而下，自左至右。 k=4 n=24-1=15

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

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

二、二叉树及其性质(2)完全二叉树 完全二叉树 如果一棵有n个结点的二叉树， 如

果一棵有 个结点的二叉树，按与满二叉树相同 个结点的二叉树 的方式对结点进行编号,若树中 个结点和满二叉树1~n 若树中n个结点和满二叉树 的方式对结点进行编号 若树中 个结点和满二叉树 编号完全一致，则称该树为完全二叉树。 编号完全一致，则称该树为完全二叉树。

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

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

二、二叉树及其性质完全二叉树的特点 前k-1层(k为深度)是满二叉树。 前 层 为深度) 为深度 是满二叉树。 结点数 满足：2k-1-1<n≤2k-1。 结点数n满足 结点数 满足： 每个结点 的左子树深度 i减去右子树深度 i等于 或1 每个结点i的左子树深度 减去右子树深度Rh 等于0或 每个结点 的左子树深度Lh (Lhi-Rhi=0 或1)。 )。 最后一层结点是向左充满的。 最后一层结点是向左充满的 最后一层结点是向左充满 叶子只能出现在最后两层上。 叶子只能出现在最后两层上。 叶子只能出现在最后两层上 满二叉树是完全二叉树，反之不成立。 满二叉树是完全二叉树，反之不成立。 满二叉树是完全二叉树

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

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

二、二叉树及其性质看下列的树是不是完全二叉树？ 看下列的树是不是完全二叉树？

1 2 4 6Lh2-Rh2=0-1=-1

1 3 4 2 5 3

Lh1-Rh1=3-1=2

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

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

二、二叉树及其性质个结点的完全二叉树的深度为: 【性质4】具有 个结点的完全二叉树的深度为 性质 】具有n个结点的完全二叉树的深度为┗ log2n ┛+1的最大整数) (┗ x ┛表示不大于x的最大整数)

证明：设深度为k,则 证明：设深度为 ， 结点数n满足： 结点数 满足：2k-1-1 < n≤2k-1 满足 即: 2k-1≤n < 2k 于是有： 于是有：k-1 ≤log2n < k k-1和k都是整数，显然有：┗ log2n ┛=k-1 和 都是整数 显然有： 都是整数， 即：k= ┗ log2n ┛+1

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

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

二、二叉树及其性质【性质5】如果对有 个结点的完全二叉树按层序给各 性质 】如果对有n个结点的完全二叉树按层序给各个结点编号，则对于编号为 ( 个结点编号，则对于编号为i(1≤i≤n)的结点有： )的结点有：

(1)若i=1,则i是根结点；若i>1,则i的双亲是 若 ， 是根结点 是根结点； 则 的双亲是 ┗i/2┛ 。 (2) 若2i ≤n,则i的左孩子为 ；否则 的左孩子为2i;否则(2i>n)i无 ， 的左孩子为 无 左孩子。 左孩子。 (3) 若2i+1 ≤n,则i的右孩子为 +1;否则 的右孩子为2i+ ; + 则 的右孩子为 (2i+1>n)i无右孩子。 无右孩子。 无右孩子 1 证明： 证明： 略。

2 4 5

3

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

三、二叉树的存储结构 二叉树这样的非线性结构能否用顺序 存储结构

?A B C E F G

D

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

三、二叉树的存储结构 顺序存储结构用一组地址

连续的存 储单元， 储单元，以层序顺序存放 二叉树的数据元素， 二叉树的数据元素，结点 的相对位置蕴涵着结点之 间的关系。 间的关系。

A B D E F C G

1 2 3 4 5 6 7 8 9 10 ABC D E FG 0 0 0完全二叉树的顺序存储

BT(3)=的双亲为┗3/2┛=1,即在 的双亲为 即在BT(1)。 即在 。 其左孩子为BT(2i)=BT(6) 其左孩子为 其右孩子为BT(2i+1)=BT(7) 其右孩子为