文档介绍：计算机 软件技术基础
第6讲基本数据结构及其运算 III 树
树与二叉树
树的基本概念
二叉树及其基本性质
二叉树的存储结构
二叉树的遍历
树的基本概念
树(tree)是一类重要的非线性数据结构,是以分支关系定义的层次结构。
注1:过去许多书籍中都定义树为n≥1,曾经有“空树不是树”的说法,但现在树的定义已修改。
注2:树的定义具有递归性,即树中还有树。
由n(n≥0)结点组成的有限集合T。在任意一棵非空树中,有且仅有一个结点称为根(root),当n>1时,其余的结点分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树,被称作这个根的子树。
1. 树的定义
2. 若干术语
树的基本概念
结点
结点的度
结点的层次
终端结点(叶子)
非终端结点(分支结点)
内部结点
A
B
C
D
E
F
G
H
I
J
K
L
第1层
第2层
第3层
第4层
高度为4
孩子
双亲
兄弟
祖先
子孙
堂兄弟
树的度
树的深度/高度
有序树
无序树
森林
2. 若干术语
双亲—即上层的那个结点(直接前驱)
孩子—即下层结点的子树的根(直接后继)
兄弟—同一双亲下的同层结点(孩子之间互称兄弟)
堂兄弟—即双亲位于同一层的结点(但并非同一双亲)
祖先—即从根到该结点所经分支的所有结点
子孙—即该结点下层子树中的任一结点
根—即根结点(没有前驱)
叶子—即终端结点(没有后继)
森林—指m棵不相交的树的集合(例如删除A后的子树个数)
树的基本概念
2. 若干术语—续
树的基本概念
结点—即树的数据元素
结点的度—结点挂接的子树数(有几个直接后继就是几度,亦称“次数”)
结点的层次—从根到该结点的层数(根结点算第一层)
终端结点—即度为0的结点,即叶子
分支结点—即度不为0的结点(也称为内部结点)
树的度—所有结点度中的最大值(Max{各结点的度})
树的深度—指所有结点中最大的层数(Max{各结点的层次})
有序树、无序树: 如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树。
A
B
C
D
E
F
G
H
I
J
K
L
M
结点A的度:3
结点B的度:2
结点M的度:0
叶子:K,L,F,G,M,I,J
结点A的孩子:B,C,D
结点B的孩子:E,F
结点I的双亲:D
结点L的双亲:E
结点B,C,D为兄弟
结点K,L为兄弟
树的度:3
结点A的层次:1
结点M的层次:4
树的深度:4
结点F,G为堂兄弟
结点A是结点F,G的祖先
树的基本概念
树的基本概念
3. 树的逻辑结构
(一对多(1:n),有多个直接后继(如家谱树、目录
树等等),但只有一个根结点,且子树之间互不相交
4. 树的存储结构
讨论1:树是非线性结构,该怎样存储?—仍然有顺序存储、链式存储等方式。
可规定为:从上至下、从左至右将树的结点依次存入内存。
重大缺陷:复原困难(不能唯一复原就没有实用价值)。
讨论2:树的顺序存储方案应该怎样制定?
树的基本概念
4. 树的存储结构
讨论3:树的链式存储方案应该怎样制定?
可用多重链表:一个前趋指针,n个后继指针。
细节问题:树中结点的结构类型样式该如何设计?
即应该设计成“等长”还是“不等长”?
缺点:等长结构太浪费(每个结点的度不一定相同);
不等长结构太复杂(要定义好多种结构类型)。
解决思路:先研究最简单、最有规律的树,然后设法把一般的树转化为简单树。
二叉树
树的基本概念
5. 树的运算
要明确:
1. 普通树(即多叉树)若不转化为二叉树,则运算很难实现。
2. 二叉树的运算仍然是插入、删除、修改、查找、排序等,但这些操作必须建立在对树结点能够“遍历”的基础上!(遍历——指每个结点都被访问且仅访问一次,不遗漏不重复)。
本章重点:二叉树的表示和实现