没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
第六章 树和二叉树
6.1 树(tree)的概念
在自然界和日常生活中,可以见到很多情形可以归
结为树结构。如:家族谱系、行政管理机构、Windows
磁盘文件管理系统等。
自然界的树是树根朝下,枝干和叶子向上生长,而
我们讨论的树在生长方向上正好与其相反,它是倒长
的树,即根朝上,枝干和叶子朝下。
例 1:某家族谱系的一部分
例 2:国家行政管理机构的一部分
景奇
宏恩
新民
意海
新主
意河
意江
宏福
新华
意民
宏亮
新诚
意凌
新胜
意山
意水
例 3:Windows 磁盘文件的一部分
C:\
TC20
VC6.0
数据结构课件
数据结构讲稿
第一章
第二章
……
MyTc 程序
Tc1
Tc2
……
MyVc 程序
Vc1
国务院
河北省
廊坊市
石家庄市
北京市
海淀区
西城区
昌平区
天津市
内蒙古区
Vc2
……
树是一种层次结构,属于非线性结构。我们学过的
线性表可以灵活组织数据,但它受到线性结构的限制,
表达层次结构不太方便。
6.1.1 树的定义
●树(Tree)是 n(n≥0)个结点的有限集合。它
满足:
(1)仅有一个特定的结点,称为根(root)结点;
(2)其余结点分为 m(m≥0)个互不相交的非空有限
集合
T
,1
,
T
2
,……,
T
m
,其中每个集合自身又是一棵树,
称为根的子树(subtree)。
本条即是说,树结点之间的路径不能形成回路,否
则称为图(下章介绍)。
●为了表述方便,把没有结点的树称为空树。
●树的定义具有递归性:即一棵树是由根及若干棵
子树构成的,而子树又是由根及若干棵子树构成
的,……。
●表达树的方法通常有 4 种:树形、凹入、集合和
广义表
第一种:树形表示法
第二种:凹入表示法
第三种:集合嵌套表示法
第四种:广义表表示法 T(A(B,C(E,F),D(G,H)))
A
B
C
D
E
F
G
H
B
C
E
F
D
G
H
A
○
E
C
○
F
○
G
D
○
H
B
A
6.1.3 树的基本术语
为了对树的形态表述清楚和形象,通常引用树和人
的特征及术语来描述。
(1)结点和树的度(degree)
结点所拥有的子树的个数称为该结点的度,而树中
各结点的度的最大值称为该树的度。
如:
●结点 B、E、F、G 和 H 的度数是 0;
●结点 C 和 D 的度数都是 2;
●结点 A 的度数是 3,显然它也是树的度数。
(2)叶子(leaf)结点和分支结点
度为 0 的结点称为叶子(终端)结点;度不为 0 的
结点称为分支(非终端)结点。
一棵树除了叶子结点就是分支节点。
如:
A
B
C
D
E
F
G
H
A
B
C
D
E
F
G
H
剩余31页未读,继续阅读
城北伯庸
- 粉丝: 27
- 资源: 315
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0