| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4121 人关注过本帖
标题:判断链式二叉树是否为完全二叉树
只看楼主 加入收藏
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
我只能说完全二叉树可以用线性表来存储。但对树的操作在应用在线性表上就有问题了。

倚天照海花无数,流水高山心自知。
2008-10-24 17:02
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
[bo][un]geninsf009[/un] 在 2008-10-24 13:27 的发言:[/bo]

不过就我个人觉得,如果是处理完全二叉树的情况,已经没有必要通过链式存储来实现了,
我甚至觉得完全二叉树属于线性结构,而没有必要把它列入非线性结构,所有的元素之间
只有一些标号的对应关系,例如如果下标从 ...


个人觉得你没有理解线性表是什么。

倚天照海花无数,流水高山心自知。
2008-10-24 17:02
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
所谓的线性表就是当前一个元素,如果不是头或尾结点的话,有且仅有一个前驱结点而且有且仅有一个后继结点,
可就拿完全二叉树的一个典型的例子堆来说吧,譬如一个最小堆MinHeap<T,E>,删除元素只是在堆顶(可以认为是
队头),插入元素在队尾,再通过一定的算法例如siftUp()进行调整,把最小的调整到堆顶,即对头,所以我觉得
这就是个优先级队列啊,呵呵,当然,完全二叉树本身确实是个非线性结构,这是无可厚非,因为从定义就可以判
别了,可就是觉得堆这个例子让我觉得它又是个优先级队列...呵呵,一家之言,大家讨论:-〉
2008-10-24 18:00
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
对于一个数据结构来说本身的定义是固定的,但实现方法及如何实现却有很多种。

倚天照海花无数,流水高山心自知。
2008-10-24 18:33
xiao_ou0725
Rank: 2
来 自:江苏苏州
等 级:论坛游民
帖 子:59
专家分:20
注 册:2008-10-24
收藏
得分:0 
回复 1# psso_2007 的帖子
利用数组来存放二叉树



性质:对于一个任何处于索引为 i(0<i<n-1) 的节点来说,下列条件均为真的:

i的父节点位于:(i-1)/2;

i的左子节点:(2i+1)索引位,如果2i+1>n-1,则没有左子节点;

i的佑子节点:(2i+2)索引位,如果2i+2>n-1,则没有佑子节点;



所以利用如上性质进行存储二叉树就发现如果不是完全二叉树就可能出现数组中的数据不是连续的,而是断开的,试试。
2008-10-24 21:49
快速回复:判断链式二叉树是否为完全二叉树
数据加载中...
 
   



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

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