二叉树的性质-软考在线

二叉树的性质


知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 树和图 > 树 >
被考次数：2次被考频率：低频率总体答错率：43% 知识难度系数：	由软考在线用户真实做题大数据统计生成
相关知识点：9个

性质1：二叉树第i层（i≥1）上至多有2ⁱ^-1个结点。

可用归纳法证明性质1。

性质2：深度为k的二叉树至多有2^k^-1个结点（k≥1）。

由性质1，每一层的结点数都取最大值即得

，因此性质2得证。

性质3：对任何一棵二叉树，若其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

对二叉树中结点的度求总和也就是分支的数目，而二叉树中结点总数恰好比分支数目多1，因此性质3得证。

性质4：具有n个结点的完全二叉树的深度为

。

若深度为k的二叉树有2^k^-1个结点，则称其为满二叉树。可以对满二叉树中的结点进行连续编号，约定编号从根结点起，自上而下、自左至右依次进行。即根结点的编号为1，其左孩子结点编号为2，右孩子结点编号为3，以此类推，编号为i的结点的左孩子编号为2i、右孩子编号为2i+1。

当深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。高度为3的满二叉树和完全二叉树如下图（a）~（d）所示，显然，满二叉树也是完全二叉树。

满二叉树和完全二叉树示意图

在一个高度为h的完全二叉树中，除了第h层（即最后一层），其余各层都是满的。在第h层上的结点必须从左到右依次放置，不能留空。下图所示的高度为3的二叉树都不是完全二叉树，其中，（a）中4号结点、（b）中5号结点、（c）中6号结点的左边有空结点。

非完全二叉树

显然，具有n个结点的完全二叉树的高度为

。

本知识点历年真题：

隶属试卷

题号/题型

题干

难度系数/错误率

   2021年上半年
   数据库系统工程..
   上午试卷综合知识

54%

   2021年上半年
   数据库系统工程..
   上午试卷综合知识

32%


	相关知识点：
	二叉树的存储结构树二叉树的顺序存储结构二叉树的链式存储结构二叉树的遍历叉树的定义树的定义二叉查找树最优二叉树

旗下网站群

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

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

客服

商务合作

客服邮箱service@rkpass.cn