数据结构
树的定义
第7章 树和二叉树
树是n(n>0)个结点的有限集合T，对于任意一棵非空树， 满足： (1)有且仅有一个特定的称为根的结点，根结点无前驱； (2)当n＞1时，其余结点可分为m(m＞0)个互不相交的有 限集T1，T2，….，Tm，其中每个集合本身又是一棵树， 称为根的子树。 显然：上述树的定义是一个递归定义。
树的表示方法
A
B
C
D
EFGH I
KL
M
B KEL
F
A C
G
DI
HJ M
1A
2B
3E
4K
J
4L
3F
2C
3G
2D
3H
4M
3I
3J
(A(B(E(K)(L))(F))(C(G))(D(H(M))(I)(J)))
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 12
数据结构
树的存储结构 —— 数组表示法
目录
第01章 数据结构概论 第02章 线性表 第03章 栈 第04章 队列 第05章 串 第06章 数组、特殊矩阵和广义表 第07章 树和二叉树 第08章 图 第09章 查找 第10章 排序 第11章 文件
数据结构
第7章 树和二叉树
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 2
数据结构
结点的层次加1。
树的深度：树中结点的最大层次。
森林： 是m(m>0)棵树的集合。
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 9
数据结构
树的常用术语和基本概念
1. 双亲、子女 2. 祖先、子孙 3. 兄弟、堂兄弟 4. 度（结点的度和树的度） 5. 分支结点、叶子结点 6. 开始结点、内部结点 7. 结点的层次、树的深度 8. 有序树、无序树 9. 森林
• 非线性结构： 至少存在一个数据元素有两个或两个以上的直接前 驱（或直接后继）元素的数据结构。
• 树形结构用于描述层次结构的关系，如： 人类的族谱、各种社会关系、各类分类编码； 操作系统的文件系统、编译程序的语法树； Internet中的DNS（域名系统）
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 6
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 13
数据结构
树的存储结构 —— 孩子链表表示法
第7章 树和二叉树
分别将每个结点的孩子结点连成一个链表，然后将各表 头指针放在一个表中构成一个整体结构。
优点：便于搜索后代结点； 缺点：搜索结点的祖先结点不便。
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 14
首页 上页 目录 前页 后页 末页 16
数据结构
树的双亲表示法图示
A
B
C
D
EF
G
计算机系数据结构教学组制作
第7章 树和二叉树
data parent
00
7
1A 0
2B 1
3C 1
4D 1
5E 3
6F 3
7G 3
首页 上页 目录 前页 后页 末页 17
数据结构
树的存储结构 —— 孩子表示法
第7章 树和二叉树
结点本身的值data和双亲结点在该表中的位置。
struct tnode{ datatype data; int parent;
} struct tnode treelist[maxnum];
优点：便于搜索相应结点的父结点及祖先结点； 缺点：搜索结点的孩子结点及后代结点需要搜索整个表。
计算机系数据结构教学组制作
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 7
数据结构
树的特点
第7章 树和二叉树
(1) 树的根结点无前驱结点，除根结点之外的所有结点 有且仅有一个前驱结点； (2) 树中所有结点可以有零个或多个后继结点。
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 8
2、数有据关结构基本概念：
第7章 树和二叉树
• 利用二维数组的方式表示，Array[m,n]表示一棵m个 结点、度为n的树
• 数组的行数表示树中结点的数目，列数表示树中任意 结点包含的最多的度，数组元素为当前结点的孩子结 点相应的标号
• 由于树中存在大量度小于n的结点，致使大量的数据元 素的内容为空，当树的规模较大时浪费大量存储空间
A
1. 定长结点的多重链表
B
C
D
• 所有结点都采用树的度作为 结点中指针域的个数。
EF
G
2. 不定长结点的多重链表 • 每个结点采用自己的度作为结点中指针域的个数。
计算机系数据结构教学组制作
内容简介
O 、本章目标 一、树 二、二叉树及其遍历算法 三、线索二叉树 四、树和森林 五、哈夫曼树 六、本章小结
计算机系数据结构教学组制作
第7章 树和二叉树
首页 上页 目录 前页 后页 末页 3
数据结构
目标
第7章 树和二叉树
树的定义及相关术语 二叉树的定义、存储结构和基本运算实现 二叉树遍历 二叉树与树和森林的相互转换 哈夫曼树及应用
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 4
数据结构
树
1. 树形结构 2. 树的定义 3. 树的常用术语和基本概念 4. 树的表示方法 5. 树的基本运算
第7章 树和二叉树
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 5
数据结构
树形结构：非线性结构
第7章 树和二叉树
A
结点的度：该结点所拥有的子树的数目。
叶子结点：度为0的结点。 分支结点：度不为0的结点。
B CD
树的度：树中各结点的度的最大值
子结点：某结点的子树的根， E F G H I 称为他的子结点。
父结点：该结点称为其子树根的父结点。
J
兄弟结点：具有同一父结点的子结点称为兄弟结点。
结点的层次：根结点的层次为1，其他结点的层次等于其父
数据结构
孩子链表表示法图示
第7章 树和二叉树
Data children
0A 1B 2C 3D 4E 5F 6G
1
2
3
4
5
6
A
B
C
D
EF G
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 15
数据结构
树的存储结构 —— 双亲表示法
第7章 树和二叉树
用数组T存放各个结点；
每个结点信息包括两部分：
计算机系数据结构教学组制作
第7章 树和二叉树
1 2 34
567
8
首页 上页 目录 前页 后页 末页 10
数据结构
第7章 树和二叉树
练习：写出树的叶子结点、非终端结点、各结点的度和树的深度
A
BCD E

F GH
I JK M
计算机系数据结构教学组制作
首页 上页 目录 前页 后页 末页 11
数据结构
第7章 树和二叉树