没有合适的资源？快使用搜索试试~ 我知道了~

文库首页数据库其它数据结构－树

数据结构－树

数据结构

5星 · 超过95%的资源需积分: 22 6 下载量 106 浏览量 2011-09-23 13:00:40 上传评论收藏 1.22MB PPT 举报

温馨提示

试读

64页

树是常用经典数据结构。定义、概念、性质。。。

资源推荐

资源详情

资源评论

1. 树的定义和术语

2. 二叉树 : 定义、性质、存储

3. 二叉树的遍历

4. 二叉树遍历的迭代器类

*5. 中序穿线树

6. 最优二叉树及其应用

7. 树和森林

第五章树及二叉树

树和森林

•

树： n > 0 个结点的集合，根 + 其余结点分为 m >= 0

个集合，每一个集合本身又是一棵树（子树）

•

结点的度：该结点的子树数目

•

树的度：树中各结点度数的最大值

•

叶子、父结点、儿子结点、兄弟结点

•

祖先结点：从根结点到该结点的路径上所有结点

•

层次、高度：根为 1, 依次往下数

•

有序树：规定所有结点的儿子结点次序，否则为无序树

•

森林： m >= 0 棵互不相交树的集合

其它表示方法：

1. ( A(B(L,E),C(F),D(G(I),H))

2. 类似于书籍的目录表示法。

高度定义为层数或层数－ 1 ，都可以；本书定义为层数。

B C D

E F G H

高度为 4 、度为 3 的

树

树和森林

ADT 5.1: 树的 ADT

数据及关系 :

具有相同数据类型的数据元素或结点的有限集合。树 T 的二元组形式为：

T ＝（ D ， R ）

其中 D 为树 T 中结点的集合， R 为树中结点之间关系的集合。

D ＝ {Root}∪D

其中， Root 为树 T 的根结点， D

为树 T 的根 Root 的子树集合。

R ＝ {<Root ， r

> ， i ＝ 1 ， 2 ，…， m}

其中， r

是树 T 的根结点 Root 的子树 T

的根结点。

操作 :

Constructor ：

前提：已知根结点的数据元素之值。

结果：创建一棵树。

Getroot:

前提：已知一棵树。

结果：得到树的根结点。

FirstChild ：

前提：已知树中的某一指定结点 p 。

结果：得到结点 p 的第一个儿子结点。

NextChild ：

前提：已知树中的某一指定结点 p 和它的一个儿子结点 u 。

结果：得到结点 p 的儿子结点 u 的下一个兄弟结点 v 。

例：结点总数为 3

时的所有二叉树的树

的形状

二叉树的定义

空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。

和树的区别：可为空

左右子树有序，不可颠倒

例：二叉树

二叉树的性质

•

性质 1 ：在二叉树的第 i 层上至多有 2

i-1

个结点

E F

1 层：结点个数 2

1-1

个

2 层：结点个数 2

2-1

个

3 层：结点个数 2

3-1

个

证： k = 1 时成立，设 k = i-1 时成立则当 k = i 时在二叉树的第 i 层上至多有

i-1-1

* 2 = 2

i-1

个结点

•

性质 2 ：高度为 k 的二叉树至多有 2

- 1 个结点

证：利用性质 1 ，将第 1 层至第 k 层的最多的结点数进行相加：

1 + 2 + 2

+ ………… + 2

k-2

+ 2

k-1

= 2

- 1

•

性质 3 ：二叉树的叶子结点数 n0 等于度为 2 的结点数 n2 + 1

证：设度为 1 的结点数为 n1 ，树枝的总数为 B 则： B = n-1=n0+n1+n2-1

又 B = n1+2×n2 ；原命题得证。

E F

剩余63页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

sinat_26376983

2015-04-16

very good,useful,i like it so much

zongren7

粉丝: 1
资源: 2

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

数据结构－树

数据结构 树

数据结构——树

数据结构-树

数据结构-树和图的使用

java版数据结构-树结构

C语言数据结构-树的练习题

数据结构-树的实现代码（C语言版）.rar

数据结构之树

数据结构关于树

数据结构中的树

tree的数据结构

数据结构树结构

数据结构-红黑树.zip

数据结构-树.ppt

C语言-数据结构-回文树

数据结构-树 【详尽注释】

数据结构--树与森林--思维导图.pdf

tree树形数据结构

C语言数据结构——树

数据结构树的遍历

treedb:树结构数据数据库

数据结构练习--树.docx

数据结构-抽象数据类型-树

数据结构-哈夫曼树-实验-C语言实现

数据结构 -树与二叉树

数据结构-C语言-哈夫曼树

最新资源

数据结构树

数据结构-树【详尽注释】