二叉排序树C语言实验报告.docx

《二叉排序树C语言实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、二叉排序树李一鹏PB数学系第五组1.实验题目：二叉排序树2.实验目的：了解二叉排序树的插入删除查找操作及其查找的优点。3.实验内容：令狐冲武艺高深，习得上万种技能。但会的技能多并不见得是一件好事，因为像令狐冲这样的木头脑袋并无法迅速操纵并合理运用技能。他希望在1毫秒内发动一个技能，比如他希望发动技能号为23281的吸星大法，找到吸星大法后发现它在技能库的第153个位置，于是便发动技能库第153位置的技能，也即吸星大法。后来又学了个技能号为35124的辟邪剑法，于是便加入到技能库的新学技能组里面，以后发动辟邪剑法时便会在新学技能组里面发动

2、。现在我们要做的是帮令狐冲找到某技能号技能对应技能库的位置。4.算法分析：先对数据进行一次排序方便建立二叉排序树，序列根结点是序列中点，左右孩子分别是左右两边序列的根节点。插入时如果比根结点大则插入右子树，小则插入左子树。删除时如果没有孩子则直接删除；如果有一个孩子则用孩子的数据覆盖该结点的数据，释放孩子的空间；如果有两个孩子则找左子树最右边的数据q放到父结点处，删除q.5.程序清单：#include#include#include#definenew1(node*)mallo

3、c(sizeof(node))typedefstructtreenode{intdata,something;structtreenode*left,*right;}node;inta[1000],n;node*head;voidmsort(intl,intr){//归并排序inti,m,mid;mid=(l+r+1)/2;if(mid-1>l)msort(l,mid-1);if(mid

4、i=mid;i>l;i--)a[i]=a[i-1];//移动(跟插入排序一样)a[l]=a[0];l++;mid++;if(mid>r)break;}}voidreadln(){inti;FILE*f1;f1=fopen("a300.txt","r");fscanf(f1,"%d",&n);for(i=1;i<=n;i++)fscanf(f1,"%d",&a[i]);fclose(f1);msort(1,n);}node*create(intl,intr){node*p;intmid;if(l>r)return0;p=new1;mid=

5、(l+r)/2;p->data=a[mid];p->something=mid;p->left=create(l,mid-1);p->right=create(mid+1,r);returnp;}voidwrite(node*p){if(!p)return;write(p->left);printf("%dt",p->data);write(p->right);}voidinsert(intm,node*p){node*q;if(m>p->data)if(p->right)insert(m,p->right);else{q=new1;

6、q->data=m;q->left=q->right=0;q->something=-1;p->right=q;}if(mdata)if(p->left)insert(m,p->left);else{q=new1;q->data=m;q->left=q->right=0;q->something=-1;p->left=q;}}node*search1(intm,node*p){if(!p)return0;if(mdata)returnsearch1(m,p->left);if(m>p->data)returnsearch

7、1(m,p->right);returnp;}node*searchfather(intm,node*p){if(mdata)if(p->left->data==m)returnp;elsereturnsearchfather(m,p->left);elseif(p->right->data==m)returnp;elsereturnsearchfather(m,p->right);}voiddelete1(node*p){node*q;if(!p->left)if(p->right){q=p->right;*p=*q;free

8、(q);}else{q=searchfather(p->data,head);if(q->left==p)q->left=0;elseq->right=0;free(p);}elseif(p->right)