数据结构二叉排序树操作源代码(7页).doc

-数据结构二叉排序树操作源代码：#include<iostream>using namespace std;#define TRUE 1;#define FALSE 0;typedef int T;const maxsize=50;template <class T>struct NodeT key;/*.*/;template <class T>struct bitreeNode<T> data; bitree<T> *lchild;bitree<T> *rchild;template <class T>class BSTreepublic:Node<T> *ST;int len; /无素个数bitree<T> *t;/根指针bitree<T> *f;/根指针的双亲指针bitree<T> *p;/指向查找路径上最后访问的节点BSTree();/构造函数BSTree();/析构函数void SearchBST(bitree<T> *t,T key);/二叉排序树查找void InsertBST(bitree<T> *(&t),Node<T> e);/元素插入int DeleteBST(bitree<T> *(&t),T key);/二叉排序树中元素删除int Delete(bitree<T> *(&p);/void DeleteElem(T key);/查找表元素删除void InDisplay(bitree<T> *t);/中序遍历二叉排序树void Display();/查找表显示;template <class T>BSTree<T>:BSTree()/构造函数，初始化查找表ST=new Node<T>maxsize;/顺序存放查找表len=0;t=NULL;/查找树初始化template <class T>BSTree<T>:BSTree()/析构函数，销毁查找表delete ST; len=0;delete t;cout<<"成功销毁二叉排序树n"template <class T>void BSTree<T>:SearchBST(bitree<T> *t,T key)/元素查找 if(t=NULL | key=t->data.key)if(key=t->data.key) cout<<"找到"<<key<<"的节点"<<endl;elsecout<<"不存在"<<key<<"的节点"<<endl;else if(key<t->data.key)SearchBST(t->lchild,key);elseSearchBST(t->rchild,key);template <class T>void BSTree<T>:InsertBST(bitree<T> *(&t),Node<T> e)/元素插入STlen=e;len+; p=t; while(p)if(p->data.key=e.key)cout<<"二叉排序树中已经存在值为:"<<e.key<<"的节点n"exit(1);f=p;if(e.key<p->data.key)p=p->lchild;elsep=p->rchild;p=new bitree<T>p->data=e;p->lchild=p->rchild=NULL;if(t=NULL)t=p;elseif(e.key<f->data.key)f->lchild=p;elsef->rchild=p;template <class T>int BSTree<T>:DeleteBST(bitree<T> *(&t),T key)/ 元素删除if(!t) cout<<"二叉树为空,无法删除n" return FALSE;else if(key=t->data.key)return Delete(t);else if(key<t->data.key) return DeleteBST(t->lchild,key);elsereturn DeleteBST(t->rchild,key);template <class T>int BSTree<T>:Delete(bitree<T> *(&p)bitree<T> *q,*s;if(!p->rchild)q=p;p=p->lchild;delete q;cout<<"成功删除"<<endl;else if(!p->lchild)q=p;p=p->rchild;delete q;cout<<"成功删除"<<endl;elseq=p;s=p->lchild;while(s->rchild)q=s;s=s->rchild;p->data=s->data; if(q!=p)q->rchild=s->lchild; elseq->lchild=s->lchild; delete s; cout<<"成功删除"<<endl;return TRUE;template <class T>void BSTree<T>:DeleteElem(T key)/顺序表元素删除 for(int i=0;i<len && STi.key!=key;i+);if(i<len)for(int j=i+1;j<len;j+)STi=STj;len-;template <class T>void BSTree<T>:InDisplay(bitree<T> *t)/中序遍历输出if(t!=NULL)InDisplay(t->lchild);cout<<t->data.key<<" " InDisplay(t->rchild);template <class T>void BSTree<T>:Display()/输出查找表中的数据元素cout<<"查找表中的数据元素关键字依次为:n"for(int i=0;i<len;i+)cout<<STi.key<<" "cout<<endl;void main()int m,l,i;BSTree<int> a;do cout<<"- 二叉排序树的基本操作-"<<endl; cout<<"- 1. 创建查找表 -n" <<"-2. 插入元素-n" <<"- 3. 删除元素 -n" <<"- 4. 查找元素 -n" <<"- 5. 中序遍历二叉排序树输出-n" <<"- 6. 查找表输出 -n" <<"- 7. 退出 -n" <<"请选择操作:" cin>>m; if(m=1)Node<T> e;cout<<"输入要插入的数据元素个数n"cin>>l;cout<<"输入"<<l<<"个不同的数据元素n"for(i=0;i<l;i+)cin>>e.key;a.InsertBST(a.t,e); else if(m=2)Node<T> e;cout<<"输入要插入的数据元素n"cin>>e.key;a.InsertBST(a.t,e); else if(m=3)T key;cout<<"输入要删除的数据元素:"cin>>key;a.DeleteBST(a.t,key);a.DeleteElem(key); else if(m=4)T key;cout<<"输入查找的数据元素: "cin>>key;a.SearchBST(a.t,key);else if(m=5)cout<<"中序遍历的输出结果为:n"a.InDisplay(a.t);cout<<endl;else if(m=6)cout<<"二叉排序树输出:n"a.Display();cout<<endl;else if(m=7)cout<<"结束运行!n"elsecout<<"输入代码非法,代码在0-7之间,请重新输入"<<endl;/cout<<endl;cout<<"请继续选择操作"<<endl;while(m!=7);-第 7 页-