这是我的课程设计题目，下周就要结果．麻烦知道的朋友指教．谢谢！我在后边附了已经编好的程序，可是和题目要求有一定距离，现在进行不下去了．我是一个新手，Ｃ语言学的不够好．请知道的朋友帮我完善一下程序！先谢谢大家！
二叉排序树的相关问题，具体要求如下：
（1）使用二叉链表存储二叉排序树，主要功能有：生成一棵二叉排序树T；计算二叉排序树T的平均查找长度，输出结果；插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次；输入元素x，查找二叉排序树T：若存在含x的结点，则删除该结点；否则输出信息“无x”；判断二叉排序树T是否为平衡二叉树；遍历二叉排序树等；
（2）二叉排序树至少含有10个测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）假设二叉排序树中的数据元素为整数，输入时以回车符作为结束标志等；
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int keytype;
typedef int elemtype;
typedef struct node
{
keytype key; /*关键字域*/
elemtype other; /*其他域*/
struct node *lchild, *rchild; /*左 右孩子指针*/
}*bistree; /*二叉排序树的结点结构*/
int BSTSearch (bistree t,keytype key) /*二叉排序树查找的非递归算法*/
{
bistree p;
p=t;
while(p!=NULL && p->key!=key)
{
if(key<p->key)
p=p->lchild; /*沿左子树查找*/
else
p=p->rchild; /*沿右子树查找*/
}
if(p!=NULL)
return(1);
else
return(0);
}
bistree BSTInsert(bistree t,bistree s) /*二叉排序树的插入的非递归算法*/
{
bistree p,q;
if(t==NULL) /*二叉排序树为空的情况*/
{
t=s;
return(t);
}
p=t; /*从根结点开始*/
while(p!=NULL)
{
q=p;
if(s->key==p->key) /*查找到返回*/
return(t);
else /*继续搜索*/
{
if(s->key<p->key) /*搜索左子树*/
p=p->lchild;
else /*搜索右子树*/
p=p->rchild;
}
}
if(s->key>q->key)
q->rchild=s;
else
q->lchild=s;
return(t);
}
void BSTCreat(bistree t) /*建立一个有n个节点的二叉排序树算法*/
{
bistree s;
keytype key; /*关键字*/
int i,n;
t=NULL;
printf("Please input the number of the nodes:\n");
scanf("%d",&n);
printf("Please input the data:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&key); /*假定关键字为整型*/
s=(bistree)malloc(sizeof(bistree)); /*生成一个新结点*/
s->lchild=NULL;
s->rchild=NULL;
s->key=key; /*调用插入算法将s所指结点插入二叉排序树t中*/
t=BSTInsert(t,s);
}
}
void BSTDelete(bistree t,int key) /*二叉排序树中删除一个结点的算法*/
{
bistree p,q,s;
p=t;
q=NULL; /*p指向待比较的结点，q指向p的前驱结点*/
while(p!=NULL && p->key!=key) /*查找值域为key的结点*/
if(key<p->key)
{
q=p;
p=p->lchild;
}
else
{
q=p;
p=p->rchild;
}
if(p==NULL)
printf("Can not find node %d \n",key);
else if(p->lchild==NULL) /*被删结点无左子树*/
{
if(q==NULL) t=p->rchild; /*考虑p为根结点的情况*/
else if(q->lchild==p)
q->lchild=p->rchild; /*p为双亲的左子树*/
else
q->rchild=p->rchild; /*p为双亲的右子树*/
free(p); /*释放p结点*/
}
else if(p->rchild==NULL) /*被删除结点无右子树*/
{
if(q==NULL)
t=p->rchild; /*考虑p为根结点的情况*/
else if(q->lchild==p)
q->lchild=p->rchild; /*p为双亲的左子树*/
else
q->rchild=p->rchild; /*p为双亲的右子树*/
free(p); /*释放P结点*/
}
else /*被删除结点同时有左子树和右子树*/
{ /*查找被删除结点的左子树中的最右结点，即刚好小于key的结点，也即是p的直接前驱*/
s=p->lchild;
while(s->rchild!=NULL) /*寻找p的直接前驱s*/
s=s->rchild;
s->rchild=p->rchild; /*被删除结点的右子树作为直接前驱s的右子树*/
/*被删除结点的左子树根代替被删结点*/
if(q==NULL) /*被删结点是根结点*/
t=p->lchild;
else if(q->lchild==p) /*p为其双亲结点左子树*/
q->lchild=p->lchild;
else /*p为双亲的右子树*/
q->rchild=p->lchild;
free(p);
}
}
void BSTPrint(bistree t)
{
if(t!=NULL)
{
BSTPrint(t->lchild);
printf("%d\t",t->key);
BSTPrint(t->rchild);
}
}
void main()
{
int k;
bistree p,s1;
keytype key1;
print5f("建立二叉排序树:\n");
p=NULL;
s1=NULL;
BSTCreat(p);
printf("请输入需要查找关键字:\n");
scanf("%d",&key1);
k=BSTSearch(p,key1);
if(!k)
printf("There is no such a node.\n");
else
printf("There id such a node.\n ");
printf("请输入要插入的结点关键字的值:\n");
scanf("%d",&s1->key);
p=BSTInsert(p,s1);
printf("请输入要删除的结点关键字的值:\n");
scanf("%d",&key1);
BSTDelete(p,key1);
printf("打印输出该二叉树:\n");
BSTPrint(p);
}
----------------解决方案--------------------------------------------------------
算法没注意看 。程序定义就出现大问题
void BSTDelete(bistree t,int key)
bistree 是什么类型。
结构体定义好像要用上面的 typedef struct node
bistree 仅仅是一个指向 node 类型的指针
----------------解决方案--------------------------------------------------------
谢谢fengwei,我在研究一下!
----------------解决方案--------------------------------------------------------
[QUOTE]这是我的课程设计题目，下周就要结果．麻烦知道的朋友指教．谢谢！我在后边附了已经编好的程序，可是和题目要求有一定距离，现在进行不下去了．我是一个新手，Ｃ语言学的不够好．请知道的朋友帮我完善一下程序！先谢谢大家！
二叉排序树的相关问题，具体要求如下：
（1）使用二叉链表存储二叉排序树，主要功能有：生成一棵二叉排序树T；计算二叉排序树T的平均查找长度，输出结果；插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次；输入元素x，查找二叉排序树T：若存在含x的结点，则删除该结点；否则输出信息“无x”；判断二叉排序树T是否为平衡二叉树；遍历二叉排序树等；
（2）二叉排序树至少含有10个测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）假设二叉排序树中的数据元素为整数，输入时以回车符作为结束标志等；
[/QUOTE]
在学习中,正好也可以练习下,平时对2x树关注的少!
----------------解决方案--------------------------------------------------------
二叉排序树的相关问题，具体要求如下：
（1）a:使用二叉链表存储二叉排序树，主要功能有：生成一棵二叉排序树T；
b:计算二叉排序树T的平均查找长度，输出结果；
c:插入元素x，重新计算二叉排序树T的平均查找长度以及统计各结点所在的层次；
d:输入元素x，查找二叉排序树T：
f:若存在含x的结点，则删除该结点；否则输出信息“无x”；
g:判断二叉排序树T是否为平衡二叉树；
h:遍历二叉排序树等；
（2）二叉排序树至少含有10个测试数据，算法对于这些合法的输入数据都能产生满足规格说明
要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的
结果；对算法实现过程中的异常情况能给出有效信息；
（4）假设二叉排序树中的数据元素为整数，输入时以回车符作为结束标志等；
名词解释：1#平衡二叉树：左右子树都是平衡二叉树，且左右子树的深度相差<=1.
2#二叉排序数：指的是一棵为空的二叉树，或者具有如下特性的非空二叉树：
1'若它的左子树非空，则左子树上所有的结点的值均小于根结点的值
2'若它的右子树非空，则右子树上所有的结点的值均大于根结点的值
3'左右子树又各是一棵二查排序数
*/
#define NULL 0
typedef struct bnode
{
int data;
struct bnode *left, *right;
}bnode,btree;
/**********对于课程设计条件可知道需要创建的函数如下*********/
//创建二叉树
void create(btree *b);
//输出二叉树结点元素
void print(btree *b);
//插入结点s
void insert(btree *b, btree *s);
//查找元素x，返回search类型指针
btree *search(btree *b, int x);
//删除元素x
void del(btree *b, int x);
//判断是否为平衡二叉树。
bool balencebtree(btree *b);
//先序遍历二叉树
void preorder(btree *b);
//二叉树的深度,关键是为了判断平衡二叉树
int depth(btree *b);
//二叉树的当前接点的层次
void level(btree *b,btree *p, int nodelevel,int currentlevel) //nodelevel初值为1
{
if (b == NULL)h = 0 ;
else if(p == b)nodelevel = currentlevel;
else
{
level(p, b->left,nodelevel,currentlevel+1);
if(h == -1)level(p,b->right,nodelevel,currentlevel+1);
}
}
/***********声明函数的实现*************/
/*
先讨论向二叉树中插入一个结点s的函数实现思想：
a:若b是空树，则将s所指的结点作为根结点插入，否则
b:若s->data = b(相对根结点)的数据域的值(无须插入相同的点)，则返回；否则
c:若s->data < b的数据域的值，则把s所指结点插入到左子书中；否则
d:把s所指结点插入到有子树中。
*/
void insert(btree *b, bnode *s)
{
if(b == NULL) b = s;
else
if(s->data = b->data)
return;
else
if(s->data < b->data)
insert(b->left,s);
else
if(s->data >b->data)
insert(b->right,s);
}
/*
生成二叉树的过程先有一个空树，再逐个插入，并以-1结束
*/
void create(btree *b)
{
int x;
btree *s;
b = NULL;
do
{
scanf("%d",&x); //读入一个整数
s = (bnode *)malloc(sizeof(bnode)); //开辟一个新结点s
s ->data = x;
s ->left = NULL;
s ->right = NULL;
insert(b,s);
}while(x != -1);
}
/*
输出的是有嵌套括号的二叉树。思想：
a：首先输出根结点
b：再依次输出它的左子数和右子树
c：另外，依次输出的左右子树至少有一个不为空,否则不必输出了
*/
void print(btree *b)
{
if(b != NULL)
{
printf("%d",b ->data);
if(b ->left != NULL ||b ->right != NULL) //确定左右子树不为空
{
printf("(");
print(b ->left);
if (b ->right != NULL)
printf(",");
print(b ->right);
printf(")");
}
}
}
/*
在二叉树b中查找x的过程为：
a:若b是空树，则搜索失败，否则
b:若x等于b的根结点的数据域的值，则查找成功；否则
c:若x<b的根结点的数据域的值，则搜索左子树；否则
d:查找右子树。
*/
btree *search(btree *b, int x)
{
if(b == NULL)
return(NULL);
else
{
if(b ->data == x)return(b);
if(x <b->data)return(search(b ->left,x));
else
return(search(b->right,x));
}
}
/*
在二叉树b中删除x的过程为：
a:若b是空树，则返回printf("the btree is null!");，
b:若p所指没有左子树，则用右子树的根代替被删的结点
c:若p所指结点有左子树，则在其左子树中找到最右结点r来代替被删除的结点
(即将t所指结点的右指针置成p所指结点的右子树的根，然后用p所指结点的
左子树的根结点代替被删的p所指结点)。
*/
void del(btree *b, int x)
{
btree *p; //p指向待比较的结点
btree *q; //q指向p的前驱结点
btree *r; //有左子树时的最右结点
btree *t; //无左子树时的临时结点
p = b;
q = NULL;
while(p != NULL && p ->data != x)
if(x <p->data)
{
q = p;
p = p->left;
}
else
{
q = p;
p = p ->right;
}
if (p == NULL)
{
printf("the btree is null!");
}
else
if(p ->left == NULL) //被删除结点无左子树
{
if(q == NULL)
t = p ->right;
else if(q ->left == p)
q ->left = p ->right;
else
q ->right = p ->right;
}
/************查找被删除结点的左子树中的最右结点，即刚好小于x的结点***************/
else //被删除结点有左子树
{
r = p ->left;
while(r ->right != NULL)
r = r->right;
//被删除的右子树作为r的右子树
r ->right = p ->right;
//被删除结点的左子树根代替被删结点
if(q == NULL)t = p ->left; //被删结点是根结点
else if(q ->left == p)
q ->left = p ->left;
else q ->right = p ->left;
}
}
/*
先序遍历二叉树
*/
void preorder(btree *b)
{
if(b != NULL)
{
printf("%d",b ->data);
preorder(b ->left);
preorder(b ->right);
}
}
/**************求二叉树的深度******************/
int depth(btree *b)
{
int dep1, dep2;
if(b == NULL)return 0;
else
{
dep1 = depth(b->left);
dep2 = depth(b->right);
if(dep1 > dep2)
return (dep1+1);
else
return (dep2+1);
}
}
/**************判断平衡二叉树****************/
bool balencebtree(btree *b)
{
if(b == NULL)return true;
int dep1 = depth(b->left);
int dep2 = depth(b->right);
if((dep1-dep2) > 1 || (dep2-dep1) > 1)
return false;
else
return balencebtree(b->left)&&balencebtree(b->right);
}
----------------解决方案--------------------------------------------------------
像二叉树的平均查找长度,这可以单独搞好几天了
----------------解决方案--------------------------------------------------------