| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 778 人关注过本帖
标题:关于二叉排序树!!
只看楼主 加入收藏
woaiguoguo
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2006-10-26
收藏
 问题点数:0 回复次数:7 
关于二叉排序树!!
判断一棵树是否是二叉排序树的算法
2007-01-01 12:16
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
递归判断.每次判断左子树<根<右子树.(仿前序遍历)

倚天照海花无数,流水高山心自知。
2007-01-01 15:37
woaiguoguo
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2006-10-26
收藏
得分:0 

我想知道非递归的算法,谢谢

2007-01-02 13:16
song4
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:38
帖 子:1533
专家分:4
注 册:2006-3-25
收藏
得分:0 

你把书上的修改一下就可以了


嵌入式 ARM 单片机 驱动 RT操作系统 J2ME LINUX  Symbian C C++ 数据结构 JAVA Oracle 设计模式 软件工程 JSP
2007-01-02 14:08
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

竟然当了版主,做做义务...
非递归的话,跟层序遍历二叉树差不多,引入个队列就行了.
简单代码如下:
boolean judge(Tree &T)
{
Tree p=null;
bool flag=true;
Queue q;
EnQueue(q,T);
while(!isEmpty(q)||p!=null)//当队列非空或者p非空
{
p=DeQueue(q);//出队
if(p)
{
if(p->lchild)
{
if(p->lchild->data<p->data)
EnQueue(q,p->lchild);//入队,表示继续向下执行
else
{
flag=false;
break;
}
}
if(p->rchild)
{
if(p->rchild->data>p->data)
EnQueue(q,p->rchild);
else
{
flag=false;
break;
}
}
}
}
return flag;
}

[此贴子已经被作者于2007-1-2 21:38:40编辑过]


对不礼貌的女生收钱......
2007-01-02 14:44
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
以下是引用woaiguoguo在2007-1-2 13:16:37的发言:

我想知道非递归的算法,谢谢

同样的,除了soft_wind 斑竹说的队列,也可以仿照任何一种遍历做.用栈.


倚天照海花无数,流水高山心自知。
2007-01-02 19:58
woaiguoguo
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2006-10-26
收藏
得分:0 

哦,谢谢各位!!

2007-01-08 21:47
woaiguoguo
Rank: 1
等 级:新手上路
帖 子:19
专家分:0
注 册:2006-10-26
收藏
得分:0 

好象上面的层次遍历的方法有问题呢,这样只能比较根和左右子树的根,不满足二叉搜索树的定义

2007-01-09 18:06
快速回复:关于二叉排序树!!
数据加载中...
 
   



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

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