首页
>
知识点讲解
树
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 树和图 >
被考次数：
8次
被考频率：
中频率
总体答错率：
43%
知识难度系数：
由 软考在线 用户真实做题大数据统计生成
相关知识点：5个
树结构是一种非常重要的非线性结构，该结构中一个数据元素可以有两个或两个以上的直接后继元素，可以用来描述客观世界中广泛存在的层次关系。
树的定义
树是
n
（
n
≥0）个结点的有限集合。当
n
=0时称为空树。在任一非空树（
n
>0）中，有且仅有一个称为根的结点；其余结点可分为
m
（
m
≥0）个互不相交的有限集
T
1
，
T
2
，…，
T
m
，其中每个集合又都是一棵树，并且称为根结点的子树。
树的定义是递归的，它表明了树本身的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。该定义只给出了树的组成特点，若从数据结构的逻辑关系角度来看，树中元素之间有明显的层次关系。对树中的某个结点，它最多只和上一层的一个结点（即其双亲结点）有直接关系，而与其下一层的多个结点（即其子树结点）有直接关系，如下图所示。通常，凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。
树结构示意图
.双亲、孩子和兄弟：结点的子树的根称为该结点的孩子，相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。例如，上图中，结点A是树根，B、C、D是A的孩子结点，B、C、D互为兄弟；B是E、F的双亲，E、F互为兄弟。
.结点的度：一个结点的子树的个数记为该结点的度。例如，上图中，A的度为3，B的度为2，C的度为0，D的度为1。
.叶子结点：也称为终端结点，指度为零的结点。例如，上图中，E、F、C、G都是叶子结点。
.内部结点：度不为零的结点称为分支结点或非终端结点。除根结点之外，分支结点也称为内部结点。例如，上图中，B、D都是内部结点。
.结点的层次：根为第一层，根的孩子为第二层。以此类推，若某结点在第
i
层，则其孩子结点就在第
i
+1层。例如，上图中，A在第1层，B、C、D在第2层，E、F和G在第3层。
.树的高度：一棵树的最大层次数记为树的高度（或深度）。例如，上图所示树的高度为3。
.有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
.森林：
m
（
m
≥0）棵互不相交的树的集合。
叉树的定义
二叉树是
n
（
n
≥0）个结点的有限集合，它或者是空树（
n
=0），或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树所组成。
尽管树和二叉树的概念之间有许多联系，但它们有区别。树和二叉树之间最主要的区别是：二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树，树中则不区分，如下图所示。另外，二叉树中结点的最大度为2，而树中不限制结点的度数。
二叉树与普通树
二叉树的性质
性质1：
二叉树第
i
层（
i
≥1）上至多有2
i
-1
个结点。
可用归纳法证明性质1。
性质2：
深度为
k
的二叉树至多有2
k
-1
个结点（
k
≥1）。
由性质1，每一层的结点数都取最大值即得
，因此性质2得证。
性质3：
对任何一棵二叉树，若其终端结点数为
n
0
，度为2的结点数为
n
2
，则
n
0
=n
2
+1。
对二叉树中结点的度求总和也就是分支的数目，而二叉树中结点总数恰好比分支数目多1，因此性质3得证。
性质4：
具有
n
个结点的完全二叉树的深度为
。
若深度为
k
的二叉树有2
k
-1
个结点，则称其为满二叉树。可以对满二叉树中的结点进行连续编号，约定编号从根结点起，自上而下、自左至右依次进行。即根结点的编号为1，其左孩子结点编号为2，右孩子结点编号为3，以此类推，编号为
i
的结点的左孩子编号为2
i
、右孩子编号为2
i
+1。
当深度为
k
、有
n
个结点的二叉树，当且仅当其每一个结点都与深度为
k
的满二叉树中编号为1~
n
的结点一一对应时，称之为完全二叉树。高度为3的满二叉树和完全二叉树如下图（a）~（d）所示，显然，满二叉树也是完全二叉树。
满二叉树和完全二叉树示意图
在一个高度为
h
的完全二叉树中，除了第
h
层（即最后一层），其余各层都是满的。在第
h
层上的结点必须从左到右依次放置，不能留空。下图所示的高度为3的二叉树都不是完全二叉树，其中，（a）中4号结点、（b）中5号结点、（c）中6号结点的左边有空结点。
非完全二叉树
显然，具有
n
个结点的完全二叉树的高度为
。
二叉树的存储结构
二叉树的顺序存储结构
用一组地址连续的存储单元存储二叉树中的结点，必须把结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。对于深度为
k
的完全二叉树，除第
k
层外，其余各层中含有最大的结点数，即每一层的结点数恰为其上一层结点数的两倍，由此从一个结点的编号可推知其双亲、左孩子和右孩子的编号。
假设有编号为
i
的结点，则有：
.若
i
=1，则该结点为根结点，无双亲；若
i
>1，则该结点的双亲结点为
。
.若2
i
≤
n
，则该结点的左孩子编号为2
i
，否则无左孩子。
.若2
i
+1≤
n
，则该结点的右孩子编号为2
i
+1，否则无右孩子。
完全二叉树的顺序存储结构如下图（a）所示。
二叉树的顺序存储结构
显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以结点在存储单元中的位置来表示结点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的“虚结点”，这将造成空间的浪费，如上图（b）所示。
在最坏的情况下，一个深度为
h
且只有
h
个结点的二叉树（单枝树）却需要
2
h
-1个存储单元。
二叉树的链式存储结构
由于二叉树中结点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表（即一个结点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根结点，如下图所示。
二叉树的链式存储结构
设结点中的数据元素为整型，则二叉链表的结点类型定义如下：
二叉树的遍历
遍历是按某种策略访问树中的每个结点，且仅访问一次。
由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根结点、左子树和右子树三部分构成，因此若能依次遍历这三个部分的信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，依据访问根结点位置的不同，可得到二叉树的前序、中序和后序三种遍历方法。
中序遍历二叉树的操作定义如下。若二叉树为空，则进行空操作。否则：
（1）中序遍历根的左子树。
（2）访问根结点。
（3）中序遍历根的右子树。
【函数】
二叉树的中序遍历算法。
实际上，将中序遍历算法中对根结点的访问操作放在左子树的遍历之前或右子树的遍历之后，就分别得到先序遍历和后序遍历算法。遍历二叉树的过程实质上是按一定规则，将树中的结点排成一个线性序列的过程。
遍历二叉树的基本操作就是访问结点，不论按照哪种次序遍历，对含有n个结点的二叉树，遍历算法的时间复杂度都为O（n）。因为在遍历的过程中，每进行一次递归调用，都是将函数的“活动记录”压入栈中，因此，栈的容量恰为树的高度。在最坏情况下，二叉树是有n个结点且深度为
n
的单枝树，遍历算法的空间复杂度也为O（n）。
设二叉树的根结点所在层数为1，二叉树的层序遍历就是从树的根结点出发，首先访问第1层的树根结点，然后从左到右依次访问第二层上的结点，其次是第三层上的结点，以此类推，自上而下、自左至右逐层访问树中各层结点的过程就是层序遍历。
最优二叉树
最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树。
从树中一个结点到另一个结点之间的通路称为结点间的路径，该通路上分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积。
树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为：
其中，
n
为带权叶子结点数目，
w
k
为叶子结点的权值，
l
k
为叶子结点到根结点的路径长度。
最优二叉树是指权值为
w
1
，
w
2
，…，
w
n
的
n
个叶子结点的二叉树中带权路径长度最小的二叉树。例如，在下图中所示的具有4个叶子结点的二叉树中，以下图（b）所示二叉树的带权路径长度最小。
不同带权路径长度的二叉树
构造最优二叉树的哈夫曼方法如下：
（1）根据给定的
n
个权值｛
w
1
，
w
2
，…，
w
n
｝构成
n
棵二叉树的集合
F=
｛
T
1
，
T
2
，…，
T
n
｝，其中每棵树
T
i
中只有一个带权为
w
i
的根结点，其左右子树均空。
（2）在
F
中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
（3）从
F
中删除这两棵树，同时将新得到的二叉树加入到
F
中。
重复（2）、（3）步，直到
F
中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
最优二叉树的一个应用是对字符集中的字符进行编码和译码。
对给定的字符集
D
=｛
d
1
，
d
2
，…，
d
n
｝及权值集合
W
=｛
w
1
，
w
2
，…，
w
n
｝，构造其哈夫曼编码的方法为：以
d
1
，
d
2
，…，
d
n
作为叶子结点，
w
1
，
w
2
，…，
w
n
作为对应叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上0，右分支标上1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的0、1字符组成的串。
例如，设有字符集｛
a
，
b
，
c
，
d
，
e
｝及对应的权值集合｛0.30，0.25，0.15，0.22，0.08｝，按照构造最优二叉树的哈夫曼方法：先取字符
c
和
e
所对应的结点构造一棵二叉树（根结点的权值为
c
和
e
的权值之和），然后与
d
对应的结点分别作为左、右子树构造二叉树，之后选
a
和
b
所对应的结点作为左、右子树构造二叉树，最后得到的最优二叉树（哈夫曼树）如下图所示。其中，字符
a
的编码为00，字符
b
、
c
、
d
、
e
的编码分别为01、100、11、101。译码时就从树根开始，若编码序列中当前编码为0，则进入当前结点的左子树，为1则进入右子树，到达叶子时一个字符就翻译出来了，然后再从树根开始重复上述过程，直到编码序列结束。例如，若编码序列101110000100对应的字符编码采用下图所示的树进行构造，则可翻译出字符序列"edaac"。
哈夫曼树及编码示例
二叉查找树
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。
（1）若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值；
（2）若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值；
（3）左、右子树本身就是两棵二叉查找树。
一棵二叉查找树如下图（a）所示。下图（b）所示的二叉树不是二叉查找树，因为46比54小，它应该在根结点54的左子树上。
二叉查找树与非二叉查找树
从二叉查找树的定义可知，对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。
相关知识点：
图的定义及术语
邻接矩阵表示法
图的存储结构
图
邻接链表表示法
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师
系统分析师
系统架构设计师
网络规划设计师
系统规划与管理师
初级资格科目
程序员
网络管理员
信息处理技术员
信息系统运行管理员
中级资格科目
系统集成项目管理工程师
网络工程师
软件设计师
信息系统监理师
信息系统管理工程师
数据库系统工程师
多媒体应用设计师
软件评测师
嵌入式系统设计师
电子商务设计师
信息安全工程师
本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。
工作时间：9:00-20:00
客服
商务合作
客服邮箱
service@rkpass.cn
京B2-20210865
|
京ICP备2020040059号-5
|
京公网安备 11010502032051号
|
营业执照
| Copyright ©2000-2023 All Rights Reserved 软考在线版权所有
