计算机软件技术基础3-3 数据结构及算法(树与图)

第三章常用数据结构及其运算

合肥工业大学 计算机信息学院软件所

目录

§3.1 概述

§3.2 线性表§3.3 栈与队

§3.4 树与二叉树§3.5 图

§3.6 查找与排序

合肥工业大学 计算机信息学院软件所

3.4 树与二叉树3.4.1 树的定义及其存储结构

3.4.2 二叉树及其性质3.4.3 二叉树的遍历

3.4.4 二叉树的应用3.4.5 小结

合肥工业大学 计算机信息学院软件所

3.4.1 树的定义及其存储结构 什么是树？ 非线性数据结构 元素结点之间存在分支和层次关系。(一对多) 应用：家谱 社会组织机构 书的章节划分 操作系统中的多级目录结构 高级语言中源程序的语法结构等。4

合肥工业大学 计算机信息学院软件所

3.4.1 树的定义及其存储结构1. 树的定义(递归定义)树是由n(n≥0)个结点组成的有限集合T: 有且仅有一个结点称为根结点(root) 其余结点分为m(m≥0)个各互不相交的有限集合 T1、 T2、…、Tm,其中每一个集合Ti本身又是一棵树，称为 根结点root的子树。 root A n=0时，为空树。T1

B F L

C GT2

D H I J MT35

E

K

合肥工业大学 计算机信息学院软件所

3.4.1 树的定义及其存储结构rootT

A C D H I J MT3

1 2 3 4

B F L

2. 常用术语1)结点：表示树中的元素。 K

1

E

GT2

2)度：结点拥有的子树数。如A的度为3,B 的度为2。树的度=树中最大的结点度数。3)叶子(终端结点):度为0的结点。 4)孩子：结点的子树的根(后继结点)。每个结点 均是其前驱结点的孩子。 5)双亲：一个结点的前驱结点。合肥工业大学 计算机信息学院软件所6

3.4.1 树的定义及其存储结构6)子孙：以某结点为根的子树中的任一结点。 7)祖先：从根到该结点所经分支上的所有结点。 8)兄弟：同一双亲的孩子。 9)结点的层次：根为第一层，根的直接后继结点为 第二层，以此类推。 10)深度：树中结点的最大层次数。 rootT1

A C D H I J MT3

1 2 3

B F L

E

GT2

K

47

合肥工业大学 计算机信息学院软件所

3.4.1 树的定义及其存储结构rootT1

A C D H I J MT3

1 2 3 4

B F L

E

GT2

K

11)森林：是m(m≥0)棵互不相交的树的集合 12)有序树：树中结点在同层中按从左到右有序排 列、不能互换的称为有序树；反之称为无序树。 A A 例： 有序树：T1!=T2 B C C B 无序树：T1=T2 T1 T2合肥工业大学 计算机信息学院软件所8

3.4.1 树的定义及其存储结构例：用有序树表示算术表达式

(A+B)×5 / (2×(C-D))/

*+ A 5 2

*C D

B

合肥工业大学 计算机信息学院软件所

3.4.1 树的定义及其存储结构3. 树的存储结构(链式)·A · · ·B ·^ ^ C ^ · D ^ ^ ^

结点的结构类型： ^ E ^ ^^ F ^ ^^ G ^ ^ 1) 异构型-根据结点的度数

设置 相应的指针域。 例(空链域问题):一棵具有n特点：节省空间、运算不便。

2) 同构型-每个结点的指针域个 数均为树的度数。特点：运算方便、浪费空间。

个结点的k叉树，采用同构 型存储结构，问有多少个空 链域？ 解：总链域=nk;非空链域 =n-1; 所以，空链域=n(k-1)+1。

若树度为k, k=1为线性表，k=2 时空链域最低，即二叉树。合肥工业大学 计算机信息学院软件所10

3.4.2 二叉树及其性质1. 二叉树的定义及其存储结构 二叉树是n(n≥0)个结点的有限集合，它或为空树(n=0), 或由一个根结点和两棵分别称为左子树和右子树的互不 相交的二叉树构成。(递归定义。) 即：度<=2的有序树 特点：每个结点至多有2个孩子，结点度数最大为2; 结点子树有左右之分。 存储结构：采用二叉链表存储。 结点结构： Lchild Data Rchild B C D A B ^C^ D A^

E

F

^E^

^F^11

合肥工业大学 计算机信息学院软件所

3.4.2 二叉树及其性质1. 二叉树的定义及其存储结构 二叉树的五种形态 A A B B B C A A

思考：二叉树与二叉有序树的区别？ 二叉树可以是空的，而二次有 序树至少有一个结点的度为2。合肥工业大学 计算机信息学院软件所12

3.4.2 二叉树及其性质2. 二叉树的基本性质(1)二叉树的第i层上至多有2i-1(i≥1) 个结点。(可用归纳法证明)证明：当k=1时，命题显然成立。假定k=n-1时 命题成立，则第n层(k=n)的结点数最多是第 n-1层的2倍，所以第n层最多有2*2n-2=2n-1个结 点。命题成立。

1 2 4 5 6 12 8 9 10 11 3 7

(2)深度为h的二叉树中至多含有2h - 1个结点(h>=1)。证明：根据性质1容易知道深度为h的二叉树最多有20+21+…+2h-1个结点， 即最多有2h-1个结点。

合肥工业大学 计算机信息学院软件所

3.4.2 二叉树及其性质(3)包含n(n>0)个结点的二叉树总的分支数为n-1证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子 结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支， 因此二叉树总的分支数为n-1。

(4)任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结 点，则必存在关系式n0=n2+1证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为： n0 + n1 + n2 (2-2) 再看看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的 结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支 进入。因此二叉树的分支数加1就是结点总数 …… 此处隐藏：1091字，全部文档内容请下载后查看。喜欢就下载吧 ……