完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义,

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

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

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

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

概念我基本上能明白,但是,如何判断我居然写不出来。哎,这样简单的数据结构题,居然不会。

于是我google 了好一阵子,找了十几个算法,解决方案基本上是判断,有右子树,就不能有左子树,等等。基本上是反证法,找反例,由于,可能性有很多,仔细以推敲这些算法都有漏洞。这让我想起必须从不同的角度来思考这个问题。

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

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

这样代码就非常的简单了:

代码是PHP代码,只拷贝了核心的部分。$this->root 保存了树的根。

这个判断方法,暂时没有找到什么漏洞,欢迎博客园的朋友们给我一个更加好的解决方案。

本文分享自微信公众号 - Golang语言社区(Golangweb)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏彭湖湾的编程世界

【算法】赫夫曼树(Huffman)的构建和应用(编码、译码)

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

76050
来自专栏SeanCheney的专栏

《大话数据结构》总结第一章 绪论第二章 算法第三章 线性表第四章 栈和队列第五章 字符串第六章 树第七章 图第八章 查找第九章 排序

第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章 算法 算法的特性:有穷性、确定性、可行性、输...

39050
来自专栏我是攻城师

数据结构之树

树(Tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关...

17920
来自专栏mathor

树形DP

 假设现在有一棵树,我只要求出每个结点作为头节点对应子树的最大值和最小值,那么最终答案一定在其中,因此每个结点都有两个信息,最大值和最小值,我把这个信息封装为一...

17240
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

13530
来自专栏JavaEdge

二分查找复杂度分析实战演练

37280
来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

10830
来自专栏机器之心

资源 | 从算法到数据结构,百道面试问题实现答案集合

选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

29860
来自专栏小樱的经验随笔

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严...

35840
来自专栏fangyangcoder

leetcode(二)

给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。

17720

扫码关注云+社区

领取腾讯云代金券