怎样推断一棵二叉树是全然二叉树

全栈程序员-站长 • 2021年12月1日上午7:00 • 未分类 • 阅读 53

怎样推断一棵二叉树是全然二叉树

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

严蔚敏那本教材上的说法：一个深度为k，节点个数为 2^k – 1 的二叉树为满二叉树。这个概念非常好理解，

就是一棵树，深度为k，而且没有空位。

首先对满二叉树依照广度优先遍历（从左到右）的顺序进行编号。

一颗深度为k二叉树，有n个节点，然后，也对这棵树进行编号，假设全部的编号都和满二叉树相应，那么这棵树是全然二叉树。

怎样推断一棵二叉树是全然二叉树

随意的一个二叉树，都能够补成一个满二叉树。这样中间就会有非常多空洞。在广度优先遍历的时候，假设是满二叉树，或者全然二叉树，这些空洞是在广度优先的遍历的末尾，所以，但我们遍历到空洞的时候，整个二叉树就已经遍历完毕了。而假设，是非全然二叉树，

我们遍历到空洞的时候，就会发现，空洞后面还有没有遍历到的值。这样，仅仅要依据是否遍历到空洞，整个树的遍历是否结束来推断是否是全然的二叉树。

算法例如以下：

bool is_complete(tree *root)<br />{<br /> queue q;<br /> tree *ptr;<br /> // 进行广度优先遍历（层次遍历），并把NULL节点也放入队列<br /> q.push(root);<br /> while ((ptr = q.pop()) != NULL)<br /> {<br /> q.push(ptr->left);<br /> q.push(ptr->right);<br /> }</p> <p> // 推断是否还有未被訪问到的节点<br /> while (!q.is_empty())<br /> {<br /> ptr = q.pop();</p> <p> // 有未訪问到的的非NULL节点，则树存在空洞，为非全然二叉树<br /> if (NULL != ptr)<br /> {<br /> return false;<br /> }<br /> }</p> <p> return true;<br />}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118806.html原文链接：https://javaforall.net

赞 (0)

全栈程序员-站长

0 0

python中的merge函数_Python Merge函数原理及用法解析[通俗易懂]

python中的merge函数_Python Merge函数原理及用法解析[通俗易懂]Merge函数的用法jfz免费资源网简单来说Merge函数相当于Excel中的vlookup函数。当我们对2个表进行数据合并的时候需要通过指定两个表中相同的列作为key，然后通过key匹配到其中要合并在一起的values值。jfz免费资源网然后对于merge函数在Pandas中分为1vs1,多(m)vs1，以及多(m)vs多(m)这三种场景。但是平时用的最多的往往是多vs1的这种场景。也就是说2…

全栈程序员-站长
2022年6月3日
59
光场相机介绍_光场相机是什么

光场相机介绍_光场相机是什么魅族在flyme3.3上推出光场相机：

全栈程序员-站长
2025年5月24日
3
提高系统可用性的那些架构策略[通俗易懂]

提高系统可用性的那些架构策略[通俗易懂]系统高可用面临的挑战有哪些?1.资源不可用在实际业务中,出现资源不可用的原因种类可能很多,有的概率很低,比如网线被挖断了,机房失火,地震等等导致网络不可用,有的概率相对来说很高比如服务器硬件资源不足,服务器故障等等。这些问题都可能会导致对应的资源不可用。2.资源不均衡由于系统架构设计的时候没有针对高并发和大流量进行可伸缩设计,导致无法应对并发很大的场景,出现系统瘫痪甚至崩溃。3.节点功能异常这种情况是最常见的,由于代码是人写的,bug和漏洞都是难免的,所以在实际业务中大概率会出现功能

全栈程序员-站长
2022年7月13日
29
pt100测温电路图(ad590典型的测温电路)

PT100精密测温电路一、需求分析根据题目要求为：测温范围为0-100℃、测温精度要求为±1℃。由于铂电阻具有精度高、性能可靠、稳定性好的特点，且铂电阻的电阻相对变化率与温度的关系曲线线性度最好，故选择铂电阻作为敏感元件。而在国标中，铂电阻有几种不同的标准，如PT100、PT1000。分别对应着0摄氏度下铂电阻的阻值为100R和1000R，由于需要考虑铂电阻的自发热问题，所以尽量选择阻值小的铂电阻，故选择PT100为最终型号。二、电路设计2.1热电阻接法热电阻测温电路有多种接法，其中三线制会导致

全栈程序员-站长
2022年4月9日
77
常见手机定位方式浅谈图_夹具常见的定位方式

常见手机定位方式浅谈图_夹具常见的定位方式前段时间在知乎上回答了一个关于手机定位相关的问题，被一个知友问到“加一个人微信聊天之后，收到了人家的一个视频，随后也把这个人及他发的视频都删除了，几天后在网吧上网，被别人定位到了，勒索了一笔钱，说‘再

全栈程序员-站长
2022年8月4日
5
VB.NET章鱼哥出品—怎样解决MDI子窗口被父窗口中的控件覆盖的问题

VB.NET章鱼哥出品—怎样解决MDI子窗口被父窗口中的控件覆盖的问题

全栈程序员-站长
2022年2月6日
38

发表回复

关注全栈程序员社区公众号