| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5260 人关注过本帖
标题:如何判断完全二叉树
只看楼主 加入收藏
kiss_白水
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-6
收藏
 问题点数:0 回复次数:14 
如何判断完全二叉树
二叉树以链式结构存储,如何判断该二叉树是完全二叉树?
搜索更多相关主题的帖子: 二叉树 判断 
2008-10-15 10:20
kiss_白水
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-6
收藏
得分:0 
怎么没人啊 ,谁给个算法
非常感谢
2008-10-15 16:04
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
这个问题如果用死办法来做的话,还是比较容易实现的,
就是你首先用队列对该二叉树进行层次遍历,然后把遍历的每个结点
的指针放入一个指针数组,再看每个结点的度的情况,你就可以判断
它是否是完全二叉树了.
2008-10-15 20:38
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
按照完全二叉树性质判断吧
2008-10-15 21:31
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
感觉用数组映射一下结构树。然后遍历数组,如果数组中没有空就可说明它是满的。
呵呵,其实还有其它算法 好像书上有,我忘了,所以想了这个了法。
2008-10-16 19:23
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
[bo][un]missiyou[/un] 在 2008-10-16 19:23 的发言:[/bo]

感觉用数组映射一下结构树。然后遍历数组,如果数组中没有空就可说明它是满的。
呵呵,其实还有其它算法 好像书上有,我忘了,所以想了这个了法。

这样固然好做,但是我担心时间复杂度
2008-10-16 19:52
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
只要一次遍历,再设置个标记就OK了

倚天照海花无数,流水高山心自知。
2008-10-17 11:02
很远的那颗星
Rank: 2
等 级:新手上路
威 望:4
帖 子:544
专家分:0
注 册:2008-6-30
收藏
得分:0 
[bo][un]nuciewth[/un] 在 2008-10-17 11:02 的发言:[/bo]

只要一次遍历,再设置个标记就OK了

详细一点嘛~~~
按层次遍历..先找出结点中左右孩子都没有的第一个结点,再判断其后的结点是不是都没有左右孩子,如果是就是完全二叉树...

要效率,就用非递归.
另外...为找工作需要,建议大家写二叉树的遍历都用非递归...

Fighting~~~~~~~~
2008-10-17 21:10
很远的那颗星
Rank: 2
等 级:新手上路
威 望:4
帖 子:544
专家分:0
注 册:2008-6-30
收藏
得分:0 
当然可用公式,先求出树的高H,再计算出树的结点数N,如果满足N=2^H-1就是完全二叉树..

Fighting~~~~~~~~
2008-10-17 21:13
multiple1902
Rank: 8Rank: 8
等 级:贵宾
威 望:42
帖 子:4881
专家分:671
注 册:2007-2-9
收藏
得分:0 
[bo][un]很远的那颗星[/un] 在 2008-10-17 21:13 的发言:[/bo]

当然可用公式,先求出树的高H,再计算出树的结点数N,如果满足N=2^H-1就是完全二叉树..

你好,那叫满二叉树。
2008-10-17 21:21
快速回复:如何判断完全二叉树
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020214 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved