二叉树-软考在线

二叉树


知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 树 > 树 >
被考次数：47次被考频率：高频率总体答错率：40% 知识难度系数：	由软考在线用户真实做题大数据统计生成
考试要求：掌握相关知识点：1个

二叉树的定义

二叉树（Binary Tree）是n(n≥0)个节点的有限集合，它或者是空树（n=0），或者是由一个根节点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。

二叉树与树的区别如下。

.二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

.二叉树的节点的最大度为2，而树中不限制节点的度数。

二叉树的运算

二叉树的基本运算是遍历，其他运算可建立在遍历运算的基础上。

二叉树的性质

二叉树具有以下性质。

（1）二叉树第i层上的节点数目最多为2ⁱ^-1(i≥1)个。

（2）深度为k的二叉树至多有2^k-1(k≥1)个节点。

（3）在任意一棵二叉树中，若终端节点数为n₀，度为2的节点数为n₂，则n₀=n₂+1。

（4）具有n个节点的完全二叉树的深度为[log₂n]+1。

（5）对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号，则对任意节点i有以下性质。

.若i=1，则节点i是二叉树的根，无双亲；若i>1，则其双亲为

。

.若2i>n，则节点i无左孩子；否则其左孩子为2i。

.若2i+1>n，则节点i无右孩子；否则其右孩子为2i+1。

若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。

深度为k、有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时，称之为完全二叉树。

二叉树的存储结构

1）顺序存储结构

用一组地址连续的存储单元存储二叉树中的数据元素，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。

顺序存储结构用于完全二叉树时既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的"虚节点"，这将造成空间的浪费。

2）链式存储结构

由于二叉树中的节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表来存储二叉树，链表的头指针指向二叉树的根节点。

二叉树的遍历

遍历是指按某种策略访问树中的每个节点，且仅访问一次。由于二叉树所具有的递归性质，一棵非空的二叉树可以看作由根节点、左子树和右子树三部分构成，因此若能依次遍历这三部分中的每个节点信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，根据访问根节点位置的不同，可得到二叉树的前序、中序和后序3种遍历方法。

遍历二叉树的基本操作就是访问节点，不论按照哪种次序遍历，对含有n个节点的二叉树，遍历算法的时间复杂度都为O(n)。在最坏情况下，二叉树是有n个节点且深度为n的单枝树，遍历算法的空间复杂度也为O(n)。

遍历二叉树的过程实质上是按一定规则，将树中的节点排成一个线性序列的过程，因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中，有且仅有一个起始点和一个终节点，其余节点有且仅有唯一的直接前驱和直接后继。

对二叉树还可以进行层序遍历。层序遍历就是从树的根节点出发，首先访问第1层的树根节点，然后从左到右依次访问第2层上的节点，以此类推，自上而下、自左到右逐层访问树中各层上节点的过程。

线索二叉树

若n个节点的二叉树采用链表作存储结构，则链表中含有n+1个空指针域，利用这些空指针域来存放指向节点的前驱和后继信息。线索链表的节点结构如下图所示。

线索链表的节点结构

若二叉树的二叉链表采用上图所示的节点结构，则相应的链表称为线索链表，其中指向节点前驱、后继的指针称为线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

二叉树的应用：最优二叉树

霍夫曼树又称最优二叉树，是一类带权路径长度最短的树。

路径：是指从树中一个节点到另一个节点之间的通路，路径上的分支数目称为路径长度。

树的路径长度：是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。

树的带权路径长度：指树中所有叶子节点的带权路径长度之和，记为

式中，n为带权叶子节点的数目；w_i为叶子节点的权值；l_i为叶子节点到根的路径长度。

霍夫曼树是指权值为w₁，w₂，…，w_n的n个叶子节点的二叉树中带权路径长度最小的二叉树。

构造最优二叉树的霍夫曼算法如下。

（1）根据给定的n个权值w₁，w₂，…，W_n构成n棵二叉树的集合F={T₁,T₂,…,T_n}，其中每棵二叉树T_i中只有一个带权为w_i的根节点，其左右子树均空。

（2）在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。

（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。

重复（2）、（3），直到F中只含一棵树时为止。这棵树便是霍夫曼树。

树和森林

1）树的存储结构

.树的双亲表示法：用一组地址连续的单元存储树的节点，并在每个节点中附设一个指示器，指示其双亲节点在该存储结构中的位置。显然这种表示对于求指定节点的双亲或祖先都十分方便，但对于求指定节点的孩子及后代则需要遍历整个数组。

.树的孩子表示法：在存储结构中用指针指示出节点的每个孩子，由于树中每个节点的子树数目不尽相同，因此在采用链式存储结构时可以考虑多重链表。

.树的孩子兄弟表示法：又称二叉链表表示法。在链表的节点中设置两个指针域分别指向该节点的第一个孩子和下一个兄弟。利用这种存储结构便于实现树的各种操作。

2）树和森林的遍历

（1）树的遍历。树的遍历分为先根遍历和后根遍历两种。

.先根遍历：先访问树的根节点，然后依次先根遍历根的各棵子树。对树的先根遍历等同于对转换所得的二叉树进行先序遍历。

.后根遍历：先依次后根遍历树根的各棵子树，然后访问树根节点。树的后根遍历等同于对转换所得的二叉树进行中序遍历。

（2）森林的遍历。森林的遍历分为前序遍历和后序遍历两种。

.前序遍历森林：若森林非空，访问森林中第一棵树的根节点，前序遍历第一棵子树根节点的子树森林，再前序遍历除第一棵树之外剩余的树所构成的森林。

.后序遍历森林：若森林非空，后序遍历森林中第一棵树的子树森林，访问第一棵树的根节点，后序遍历除第一棵树之外剩余的树所构成的森林。

3）树、森林与二叉树的转换

（1）树、森林转换为二叉树。利用树的孩子兄弟表示法可导出树与二叉树的对应关系，在树的孩子兄弟表示法中，从物理结构上看与二叉树的二叉链表表示法相同，因此就可以用这种同一存储结构的不同解释将一棵树转换为一棵二叉树。

将一个森林转换为一棵二叉树的方法是：先将森林中的每一棵树转换为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树的左子树作为转换后二叉树根的左子树，第二棵树作为转换后二叉树根的右子树，第三棵树作为转换后二叉树根的右子树的右子树，以此类推，森林就可以转换为一棵二叉树。

（2）二叉树转换为树和森林。若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式，二叉树根的右子树又可以看作一个由森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到了一个森林。为了进一步得到树，可用树的二叉链表表示的逆方法，即节点的右子树的根、右子树的右子树的根……找出原本是同一个双亲的兄弟。二叉树转换为树或森林是唯一的。

本知识点历年真题：

隶属试卷

题号/题型

题干

难度系数/错误率

   2024年上半年
   软件设计师
   上午试卷综合知识

第12题
选择题

当一棵非空二叉树的( )时，对该二叉树进行中序遍历和后序遍历所得的序列相同。

20%

   2023年上半年
   软件设计师
   上午试卷综合知识

第61题
选择题

设由三棵树构成的森林中，第一棵树、第二棵树和第三棵树的结点总数分别为n1、n2和n3。将该森林转换为一棵二叉树，那么该二叉树的右子树包含（）个结点。

51%

>> 更多本知识点历年真题


	相关知识点：
	树的定义及基本运算

	软考在线指南
	优惠劵及余额
	在线支付
	修改密码
	下载及使用
	购买流程
	取消订单

	联系我们
	关于我们
	联系我们
	商务合作

旗下网站群

高级资格科目
信息系统项目管理师	系统分析师
系统架构设计师	网络规划设计师
系统规划与管理师
初级资格科目
程序员	网络管理员
信息处理技术员	信息系统运行管理员

中级资格科目
系统集成项目管理工程师	网络工程师
软件设计师	信息系统监理师
信息系统管理工程师	数据库系统工程师
多媒体应用设计师	软件评测师
嵌入式系统设计师	电子商务设计师
信息安全工程师

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。

工作时间：9:00-20:00

客服

商务合作

客服邮箱service@rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5 |