BST.rar_bst

#include <iostream> #include<iomanip> #include <time.h> #include <ctype.h> #include <queue> using namespace std; typedef struct { int key; }ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; } BiTNode, * BiTree; queue <int> Q; //将指针S所指的结点插入到根结点指针为T的二叉排序树中 void Insert_BST( BiTree &, BiTree); //输入一组数据元素的序列，构造二叉排序树 void Creat_BST( BiTree &); //二叉排序树上的查找（动态查找） int Searh_BST( BiTree, int); //删除二叉排序树的根结点 void DelNode ( BiTree &, BiTree, BiTree); //二叉排序树的删除 int Delete_BST( BiTree &,int); //中序遍历二叉排序树 void InOrder(BiTree); //提示用户的输入选择 int Choice(); //按一定格式输出表中的数据 void Print(BiTree); int main ( ){ int a,key,find,del; BiTree T,S; Creat_BST(T); Print(T); a = Choice (); while(a != 5){ switch(a){ case 1: cout<<"请输入你要查找的元素："; cin>>key; find = Searh_BST(T,key); if(find) cout<<"有你要找的元素。"; else cout<<"对不起，没有你要找的元素，这个元素现在已经插入到表中！"; Print(T); a=Choice(); break; case 2: cout<<"输入你要插入的元素："; cin>>key; S = new BiTNode; S->lchild = S->rchild = NULL; S->data.key = key; Insert_BST(T, S); Print(T); a=Choice(); break; case 3: cout<<"输入你要删除的元素："; cin>>key; del = Delete_BST(T, key); if(del) cout<<"元素已经删除！"; else cout<<"要删除的元素不存在！"; Print(T); a=Choice(); break; case 4: Print(T); a=Choice(); break; default : cout<<"你的输入有误,请重新输入："; a=Choice(); break; }//switch }//while return 0; } void Insert_BST( BiTree &T, BiTree S ){ BiTree p, q; if(!T) T=S;//若根节点不存在则作为根节点 else { //否则就插入到二叉排序树中 p=T; while (p){ //寻找插入点 q = p; if (S->data.key < p->data.key) p = p->lchild; else p = p->rchild; }//while if (S->data.key < q->data.key) q->lchild = S; //插入元素节点 else q->rchild = S; }//else return; } void Creat_BST( BiTree &T ){ int total; BiTree S; T=NULL; srand(time(NULL)); total = 1 + rand()%45; for(int i=0;i<total;i++){ //生成节点 S = new BiTNode; S->data.key = 1 + rand()%100; S->lchild = S->rchild = NULL; Insert_BST( T,S );//插入节点 } return; } int Searh_BST( BiTree T, int key ){ BiTree p,q,S; p = T; while (p)//查找关键字 if (p->data.key == key ) return(1);//找到就返回1 else if ( p->data.key > key) { q=p; p=p->lchild;} else {q=p; p=p->rchild; } S = new BiTNode;//没找到则插入关键字 S->data.key = key; S->lchild=S->rchild=NULL; if (!T) T=S; else if ( q->data.key > key ) q->lchild=S; else q->rchild=S; return(0);//返回0是未找到，但实际上已经插入. } void DelNode ( BiTree &T, BiTree p, BiTree f ) { BiTree s, q ; int tag = 0 ; if (!p->lchild) s=p->rchild; else if (!p->rchild) s=p->lchild; else{ q=p; s=p->lchild; while(s->rchild){ q=s; s=s->rchild; }//while p->data=s->data; if (q==p) q->lchild=s->lchild; else q->rchild=s->lchild; free(s);tag=1; } //else 左右孩子中至少有一个不存在 if (!tag){ if ( !f ) T=s; else if ( f->lchild==p ) f->lchild=s; else f->rchild=s; free(p); return; }//if (!tag) } int Delete_BST( BiTree &T,int key){ BiTree p, f ; p=T; f=NULL; while(p){ if (p->data.key == key) { DelNode ( T, p, f ) ; return(1) ;} else if (p->data.key > key) {f=p; p=p->lchild; } else { f=p; p=p->rchild; } }//while return(0); } void InOrder(BiTree root) { if (root!=NULL){ InOrder(root ->lchild); //中序遍历左子树 Q.push(root->data.key); InOrder(root ->rchild); //中序遍历右子树 } } int Choice( ){ int a; cout<<endl<<"请选择你要的操作："<<endl; cout<<" 1.搜索元素"<<endl; cout<<" 2.插入元素"<<endl; cout<<" 3.删除元素"<<endl; cout<<" 4.查看所有元素"<<endl; cout<<" 5.退出"<<endl; cin>>a; return a; } void Print(BiTree T){ InOrder(T); cout<<"表中现在的元素为："<<endl; for(int i=1;!Q.empty();i++){ if(i%10 == 0) cout<<endl; else {cout<<setw(4)<<Q.front();Q.pop();} } }