主题:用一维数组作存储结构处理二叉排序树相关问题
sherlly
[专家分:0] 发布于 2005-07-28 12:01:00
本人已经用二叉树作存储结构实现了二叉排序树的各种功能,包括二叉排序树的生成,中序遍历,节点的查找和删除,平均查找长度,以及判断二叉排序树是否是平衡二叉树,现在需要用一维数组实现以上操作,本人程序都已经写出来了,无奈调试不通过.
请问哪位高手可以指点一下,只要帮我写出正确的生成函数即可
不是用静态链表,就是用一维数组,我自己的思路是首先定义一个数组A[100],将其初值都置为-1,然后将第一个输入的数置入A[1],以后顺序输入的数,大于A[i]的放在A[2i+1]中,小于A[i]的放在A[2i]中,但是我写的程序有问题。
请问刚才那位高手可否帮我解答一下,写出一个正确的程序,只要能够生成二叉排序树即可
回复列表 (共6个回复)
沙发
千寻e [专家分:240] 发布于 2005-07-26 17:49:00
用静态链表?
板凳
sherlly [专家分:0] 发布于 2005-07-28 12:01:00
拜托各位
3 楼
千寻e [专家分:240] 发布于 2005-07-28 19:00:00
int A[MAX] = {0}; /*没有用到的结点先放上0吧*/
int i = 1, in;
while (1)
{
scanf ("%d", &in);
if (in == 0) break; /*输入0结束*/
while (A [i] && A [i] != in && i < MAX) {
if (in < A [i])
i = i * 2;
else if (in > A [i])
i = i * 2 + 1;
}
A [i] = in;
i = 1;
}
其实我也是才学数据结构,只是把书看了看,没做什么练习,所以让我编程倒是挺为难的。
这个漏洞百出,你就凑伙了吧。其实还要检查是否越界,那个无用结点应设什么标志我也没仔细想。
不过我觉得你这个方法真不错
4 楼
sherlly [专家分:0] 发布于 2005-07-29 10:30:00
谢谢你,千寻,那个程序我已经写出来了,思路还是那个样子,程序也调通了,但是我现在还有一个问题要解决就是怎么样用程序实现一个二叉排序树是不是平衡二叉树.
球二叉排序树中每一个节点的深度的程序我已经写好了,但是我觉得如果完全按照平衡二叉树的定义去写,未免太麻烦.(其实我是觉得麻烦,还没有仔细去想),你可以帮我想想吗
5 楼
yanailang2 [专家分:0] 发布于 2006-07-01 11:59:00
你好我也正在做这个课程设计!但是有很多地方不理解!我能看一下你的程序吗?谢谢!!
6 楼
dgggy521 [专家分:0] 发布于 2006-07-29 11:22:00
我也是做这个设计,,无奈还是很多问题不是很清楚...
我来回复