随机生成树

实验目的：熟练掌握二叉排序树的创建、检索和删除。

实验要求：任选一种高级程序语言编写源程序，并调试通过，测试正确。

(二)实验主要内容

1.系统随机生成n个数，放入数组中，并在屏幕上显示输出； 2.将其n个数构成二叉排序树；

3.输入一个数并检索二叉排序树是否有其数据;

4.删除一个二叉排序树中的一个节点，并检索是否还存在此数据；

(三)主要仪器设备

PC机，Windows XP操作平台，Visual C++

(四)实验原理

操作：将系统随机生成的n个数按左边小于等于父节点，右边大于父节点排序，然后实现二叉排序树的检索、插入和删除；

(五)实验步骤与调试分析：

先创建一个二叉排序树，输入一个数并在排序树中检索是否存在其数据和次数，然后删除一个二叉排序树中的一个节点，并继续查找其数据和查找的次数

(六)实验结果与分析：

先是随机生成25个数（如图）：

然后寻找一个数，比如9：

在输入删除的一个数据节点，比如3：

然后在寻找3那个数据节点：

下图是随机生成100的二叉排序树：

还有1000的随机树：

（七）附录（源程序）：

//随机生成数的创建、寻找、删除、 #include #include #include #define NULL 0 struct node;

typedef struct node *pnode1;

struct node { int data; pnode1 lch,rch,par;//树的节点结构指针 };

typedef struct node *pnode; typedef pnode *ppnode;

int m[max];//将生成的数放入到m数组中

void data(int n) { int i; srand((unsigned)time(NULL)); for(i=0;ippnode chuangjian(ppnode tree,int n) { int i; pnode p,q,p1; p=(pnode)malloc(sizeof(struct node));//m【1】为根节点 p->data=m[0]; p->par=p->lch=p->rch=NULL; p1=p;*tree=p; for(i=1;ilch=q->par=q->rch=NULL; while(q->par==NULL) { if(m[i]<=p->data) { if(p->lch==NULL) {q->data=m[i];q->par=p;p->lch=q;} else p=p->lch; continue; } if(m[i]>p->data)

{ if(p->rch==NULL) {q->data=m[i];q->par=p;p->rch=q;} else p=p->rch; continue; } } p=p1; } return tree; }

int xunzhao(ppnode tree) { pnode p; p=*tree; int n,k=1;//k计数查找的次数 printf(\"\\n输入你要寻找的数(输入-1表示不查找)：\"); scanf(\"%d\ if(n==-1) return 0;//-1表示不查找 while(p->data!=n)//找到则推出循环 { if(ndata)//n小于时 { if(p->lch==NULL) {printf(\"没找到，与他相近的数是%d 比较次数一共有%d次.\\n\ else {p=p->lch;k++;} continue; } if(n>p->data)//n大于时 { if(p->rch==NULL) {printf(\"没找到，与他相近的数是%d 比较次数一共有%d次.\\n\ else {p=p->rch;k++;} continue; } } if(p->data==n)//找到时输出相应的位置 { int i=1; while(n!=m[i-1]) i++; printf(\"找到了,他是随机数的第%d个(从1计数) 比较次数一共有%d次.。\\n\ }

}

void delet(ppnode tree) { pnode p; p=*tree; int n,k=1; printf(\"输入删除的数据：\"); scanf(\"%d\ while(p->data!=n)//找到那个数的节点 { if(ndata) { if(p->lch==NULL) {printf(\"没有此数据 比较次数一共有%d次.\\n\ else {p=p->lch;k++;} continue; } if(n>p->data) { if(p->rch==NULL) {printf(\"没有此数据 比较次数一共有%d次.\\n\ else {p=p->rch;k++;} continue; } } printf(\"比较次数一共有%d次.\ pnode q; q=p; int x=1; if(q->lch==NULL&&q->rch==NULL&&x==1) //当删除的节点是叶子时 { if(p->par->rch->data==n) //试确定删除节点在其父亲节点的左右位置 p->par->rch=NULL; else p->par->lch=NULL; x++; } if(q->lch==NULL&&x==1) //当删除节点只有右儿子时 { p->rch->par=p->par; if(p->par->rch->data==n)//试确定删除节点在其父亲节点的左右位置 p->par->rch=p->rch; else p->par->lch=p->rch; x++; } if(q->rch==NULL&&x==1) //删除节点只有左儿子时

{ p->lch->par=p->par; if(p->par->rch->data==n)//试确定删除节点在其父亲节点的左右位置 p->par->rch=p->lch; else p->par->lch=p->lch; x++; } if(q->lch!=NULL&&q->rch!=NULL&&x==1)//删除节点既有左儿子又有右儿子时 { p=p->lch;

while(p->rch!=NULL) p=p->rch;//寻找删除节点左边树的最右端点 q->data=p->data; if(p->lch==NULL) //最右端点是叶子时 p->par->rch=NULL; if(p->lch!=NULL) //最右端点有左儿子时 { p->lch->par=p->par; p->par->rch=p->lch; } x++; } xunzhao(tree); //再一次调用寻找的函数 ，查看删除节点是否存在 }

void main() { int i; printf(\"请输入生成多少个随即数：\"); scanf(\"%d\ pnode tree; data(i);//生成数据，并输出 chuangjian(&tree,i);//生成树 xunzhao(&tree); //寻找节点 delet(&tree);//删除节点 }