当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.1 概念及术语 > 讲解
同学们好
本章，我们来学习树和二叉树
在这一章当中
我们会学习到以下七部分内容
先来看
第一部分：概念及术语，第一个概念：树
树其实就来源于我们现实世界当中的树
它是由若干结点构成的集合，为了区别于我们之前讲的数据结构
在树当中，数据元素我们称为结点
对于任意非空的树
有且仅有一个根结点Root
我们在现实世界当中，谈到树的根
都是在下面
但是在数据结构这门课当中
我们在纸上画出一棵树
往往喜欢把根画在最上面
当然
这只是一种约定
剩余的结点，可被分为若干不相交的子集
每一个子集
就是根的子树
大家看到，这里出现了一个递归的概念
子树也是树
只不过，树包含的结点数量要比原来的树要少一些
上述定义本身就是递归的
我们后面会讲到树的很多算法，其中
有一些算法，就是用递归思想实现的
因为，树的概念
它的定义本身就是递归的
如果我们从上到下看，一个结点
对应0到多个子结点
比如，我们现在从上往下看
A对应着B、C、D三个子结点
D对应着H、I、J三个子结点，有一些结点
是没有子结点的
比如F
这样的结点
我们后面会看到，它叫叶子结点
现在我们从下往上看，一个结点对应一个父结点
除了根之外
我们从下往上看
每一个结点都会引出一条边，这条边它到达的那个结点，就是该结点的父结点
比如，K、L的父结点就是E，B的父结点就是A
A这个结点，作为树的根
它比较特殊
它是没有父结点的
所以，在一棵树当中
根这个结点是比较特殊的
我们再来看其他的术语，子结点/孩子
结点的子树的根，就叫做该结点的孩子
比如H
它是D的孩子
或者说子结点
这里
之所以子结点的定义比较复杂
看起来不是那么容易理解，结点的子树的根
这是因为，我们为了用子树的概念来解释子结点
实际上，通俗一点说，一条边
它所连接的两个结点
下面的那个结点就是上面的那个结点
它的子结点或者孩子
比如E、F
它们都是B的子结点或者孩子
有一些结点是没有孩子的
比如K、L
再来看父结点或双亲结点，这个概念跟子结点/孩子是相对的概念
我们刚才说了，一条边连接的两个结点
下面的是上面的子结点
那反过来，上面的就是下面结点的双亲或者父结点
比如B
它是E、F的双亲
C是G的双亲
A作为根，它是没有双亲的
或者说没有父结点
再看分支和边
它是指父子结点之间的关系
也就是图当中给出来的
这些绿色的边
它连接了两个结点
这两个结点之间，具有包含或者隶属的关系
具体表示什么关系
取决于你的应用
结点的度，它是指结点的孩子个数，一个结点
它有几个孩子
这个结点的度就是几，注意，这个度是指结点的度
比如，A结点
它有三个孩子B、C、D
它的度
就是3，C结点
只有一个孩子G，它的度是1；G结点
它没有孩子，它的度
是0
再看树的度
整棵树也有一个度
它是指树中结点的度的最大值
比如，在这棵树当中
有两个结点的度是达到了最大值3
也就是A和D
这棵树的度就是3
如果我们在A
现有的孩子B、C、D基础之上
再加一个孩子X
这时候，整棵树的度就变成了4
当然
A的度也是4
再看叶子结点，或者说终端结点
刚才说了，有一些结点
是没有孩子的
它的度为0
度为0的结点，就是叶子结点
比如F
它没有孩子
它就是叶子结点
这完全对应着现实世界当中的叶子
因为，叶子之上是不会再长出其他东西的
除了F之外
还有G、I、J
K
L
M
它们都是叶子结点
除了叶子结点之外的那些结点，也就是至少有一个孩子的结点
叫非叶结点
或者说叫分支结点
比如D
下一个概念，兄弟，很明显
这个概念也是来源于现实世界
它是指父结点相同的结点
比如，E、F这两个结点
它们的父结点都是B
所以，E、F互称为兄弟
类似的，H、I、J它们也是兄弟
B、C、D也是兄弟
堂兄弟，是指父结点在同一层的结点
这个跟我们现实世界当中的堂兄弟可能不太一样
在数据结构这门课当中
堂兄弟仅仅要求父结点在同一层就可以了
这个要求是比较宽松的
比如，L和M
尽管，L和M它们的父结点E和H不是兄弟
但是，L和M却是堂兄弟
因为，堂兄弟只要求父结点在同一层
它们的父结点E、H是在同一层
所以，L和M是堂兄弟
这个需要注意。再看子孙，子孙实际上就是从上往下看
子树当中任意的结点，都是这个结点的子孙
比如，A的第一棵子树
也就是由B、E、F、K、L
这几个结点构成的子树
在这棵子树当中
所有的结点都是A的子孙
这跟现实世界也是一样的
祖先
跟子孙是相对的概念
它是从下往上看
如果我们从一个结点走到根，所经历的任意结点
都是这个结点的祖先
比如，我们现在从K走到A
要经历E、B、A
那E、B、A
就是K的祖先
换一个结点
从M走到根结点
经历H、D、A
那H、D、A这三个结点，都是M的祖先
结点的层次，我们规定根结点在第一层
那么，第L层结点的孩子
在L+1层，有了这个规定之后
根结点在第1层，B、C、D就在第2层
这一层就是第3层
最下一层就是第4层
这就是结点的层次
最后一个概念，树的深度或者高度
注意是树的深度和高度
它是指结点的最大层次
这棵树最下一层的结点
它的层次是4
所以，这棵树的高度
就是4
如果我们给M再加一个子结点
比如Z，那这棵树的高度就变成了5
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
