无论是一个给定的二叉树是完整的还是不 [英] Whether a given Binary Tree is complete or not
问题描述
给定一个二叉树，编写一个函数来检查给定二叉树是否为完全二叉树与否。
Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.
一个完整的二叉树是二叉树中，每个级别的，可能除了最后一个，是完全填满，所有的节点都为最左。来源：维基
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. source: wikipedia
我的做法是做BFS使用队列，算上没有节点。运行 循环直到队列不为空，但打破一旦你找到了一个 以下条件成立时：
My approach is do BFS using queue and count the no of nodes. Run a loop till the queue is not null but break once you find one of the below condition holds good:
- 在左边节点不是present为节点
- 在左边节点是present但正确的节点没有present。
现在我们可以比较一下，我们从上面的方法得到的数量和 树中的节点的原始数量。如果两者相等，则 完全二叉树别人没有。
Now we can compare the count that we get from the above approach and the original count of the nodes in the tree. If both equal then complete binary tree else not.
请告诉我的做法是否正确。谢谢你。
Please tell me whether the approach is correct or not. Thanks.
这个问题是相同的<一个href="http://stackoverflow.com/questions/1442674/how-to-determine-whether-a-binary-tree-is-complete">this.但我婉这里验证我的方法。
This question is same as that of this. But i wan to verify my method here.
编辑： 该算法是由@ 鲍里斯Strandjev验证下面。我觉得这是实现了在网络可用一些算法的最简单的算法。真诚的道歉，如果你不跟我的说法一致。
The algorithm is verified by @Boris Strandjev below. I felt this is the easiest algorithm to implement out of some algorithms available in net. Sincere apologize if you do not agree with my assertion.
推荐答案
您的算法应该解决的问题。
Your algorithm should solve the problem.
你在做什么的BFS是完全等同于绘画的树，然后跟踪节点用手指从上到下，从左到右的。当您第一次无法继续你停止与你的手指跟踪。如果你还没有计算在内的所有节点则结构并不如预期明显。
What you are doing with the BFS is entirely equivalent to drawing the tree and then tracing the nodes with your finger top-down and left-right. The first time you can not continue you stop tracing with your finger. If you have not counted all the nodes then the structure is not as expected obviously.
这篇关于无论是一个给定的二叉树是完整的还是不的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
