实验9

一、实验目的要求

1．掌握使用 Turbo C 或 VC++ 上机调试程序的基本方法； 2．掌握二叉排序树的存储、插入、删除、查找等算法的实现。 二、实验内容

# include # include # include # include # define OK 1 # define ERROR 0 typedef int KeyType; typedef int TElemType; typedef struct BiTNode //define structure BiTree { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T,int array[],int &i) //createBiTree() function { TElemType ch;

//cout<<\"Pleae input data (0 for NULL node!) : \"; //cin>>ch; ch=array[i]; i++;

if(ch==0) T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\"Overflow!\"; //no alloction return (ERROR); } T->data=ch;

CreateBiTree(T->lchild,array,i); //create lchild

CreateBiTree(T->rchild,array,i); //create rchild } return (OK);

} //CreateBiTree() end

int PreOrderTraverse(BiTree T) //PreOrderTraverse() sub-function { if(T)

{ printf(\"%d \

if (PreOrderTraverse(T->lchild)) if (PreOrderTraverse(T->rchild))

return (OK); return (ERROR); } else

return (OK); }

int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) //SearchBST() { if(!T) { p=f; return (ERROR); } else if(key==T->data) { p=T; return (OK); }

else if(keydata) SearchBST(T->lchild,key,T,p); else SearchBST(T->rchild,key,T,p); } //SearchBST() end

int InsertBST(BiTree &T,TElemType e) //InsertBST() sub-function { BiTree p;

if(!SearchBST(T,e,NULL,p)) { BiTree s;

s=(BiTree)malloc(sizeof(BiTNode));

s->data=e; s->lchild=NULL; s->rchild=NULL; if(!p) T=s;

else if(edata) p->lchild=s; else p->rchild=s; return (OK); } else return(ERROR); } //InsertBST() end

void Delete(BiTree &p) //Delete() sub-function { BiTree q,s; if(!p->data)

{ q=p; p=p->lchild; free(q); } else if(!p->lchild)

{ q=p; p=p->rchild; free(q); } else

{ q=p; s=p->lchild; while(s->rchild)

{ q=s; s=s->rchild; } p->data=s->data;

if(q!=p) q->rchild=s->lchild;

else q->lchild=s->rchild; } }

int DeleteBST(BiTree &T,TElemType key) //DeleteBST() sub-function { if(key!=49&&key!=38&&key!=13&&key!=27&& key!=65&&key!=50&&key!=52&&key!=76) return (ERROR); else

{ if(key==T->data) Delete(T);

else if(keydata) DeleteBST(T->lchild,key); else DeleteBST(T->rchild,key); return (OK); } }

void main() //main() function

{ BiTree T,p,f; TElemType e; int x; T=NULL;

cout<>x; while (x!=0) { switch (x) { case 1: cout<<\"Please input the data to insert : \"; cin>>e;

InsertBST(T,e); PreOrderTraverse(T); break; case 2: cout<<\"Please input the data to delete : \"; cin>>e;

DeleteBST(T,e); PreOrderTraverse(T); break; case 3:

cout<<\"Please input a data to search: \"; cin>>e;

if (SearchBST(T,e, f,p)) { cout<<\"Sucess to search!\\n\"; cout<data<default : break; }

cout<>x; } }

三、实验讲解

1、不采用专门的二叉树排序树生成算法，通过反复的动态插入实现二叉排序树的生成。

2、每次进行插入或删除操作后，对当前的二叉排序树进行前序遍历输出，要求学生预先写出遍历序列，进行验证。