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

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

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

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

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

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

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

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

 

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

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

算法例如以下:

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118806.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java学习之常用类篇

    Java学习之常用类篇0x00前言在开发中难免调用到各种api来开发程序,那就先来学习一下api的一些相关概念。0x01api的使用首先还是得来看看api的一个解释。API(Applic

    2021年12月11日
  • ext.apply()_vba中evaluate使用方法

    ext.apply()_vba中evaluate使用方法EXT.applyEXT.apply方法详解EXT.apply方法详解apply的用法:Ext中apply及applyIf方法的应用apply及applyIf方法都是用于实现把一个对象中的属性应用于另外一个对象中,相当于属性拷贝。不同的是apply将会覆盖目标对象中的属性,而applyIf只拷贝目标对象中没有而源对象中有的属性。apply方法的签名为“apply(Objectobj,Objectconfig,Objectdefaults):Object”,该方法包含

  • “狗屁不通文章生成器”登顶GitHub热榜,分分钟写出万字形式主义大作

    “狗屁不通文章生成器”登顶GitHub热榜,分分钟写出万字形式主义大作一、垃圾文字生成器介绍最近在浏览GitHub的时候,发现了这样一个骨骼清奇的雷人项目,而且热度还特别高。项目中文名:狗屁不通文章生成器 项目英文名:BullshitGenerator根据作者的介绍,他是偶尔需要一些中文文字用于GUI开发时测试文本渲染,因此开发了这个废话生成器。但由于生成的废话实在是太过富于哲理,所以最近已经被小伙伴们给玩坏了。他的文风可能是这样的:你发现,…

  • IDEA中mybatis generator使用[通俗易懂]

    1.在对应服务的pom.xml文件中添加依赖<build><plugins><plugin><groupId>org.mybatis.gener

  • java是哪个公司的

    java一开始是Sun Microsystems公司开发的,但是在​2009年4月20日甲骨文(ORACLE)以现金收购Sun微系统公司,所以现在java属于甲骨文公司。

  • 初识 GTK

    初识 GTKGTK+是一种函数库是用来帮助制作图形交互界面的。整个函数库都是由C语言来编写的。GTK+函数库通常也叫做GIMP工具包。

发表回复

您的电子邮箱地址不会被公开。

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