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

《数据结构二叉排序树操作源代码(7页).doc》由会员分享，可在线阅读，更多相关《数据结构二叉排序树操作源代码(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构二叉排序树操作源代码：#includeusing namespace std;#define TRUE 1;#define FALSE 0;typedef int T;const maxsize=50;template struct NodeT key;/*.*/;template struct bitreeNode data; bitree *lchild;bitree *rchild;template class BSTreepublic:Node *ST;int len; /无素个数bitree *t;/根指针bitree *f;/根指针的双亲指针bitree *p;/指向查找

2、路径上最后访问的节点BSTree();/构造函数BSTree();/析构函数void SearchBST(bitree *t,T key);/二叉排序树查找void InsertBST(bitree *(&t),Node e);/元素插入int DeleteBST(bitree *(&t),T key);/二叉排序树中元素删除int Delete(bitree *(&p);/void DeleteElem(T key);/查找表元素删除void InDisplay(bitree *t);/中序遍历二叉排序树void Display();/查找表显示;template BSTree:BSTree

3、()/构造函数，初始化查找表ST=new Nodemaxsize;/顺序存放查找表len=0;t=NULL;/查找树初始化template BSTree:BSTree()/析构函数，销毁查找表delete ST; len=0;delete t;cout成功销毁二叉排序树n;template void BSTree:SearchBST(bitree *t,T key)/元素查找 if(t=NULL | key=t-data.key)if(key=t-data.key) cout找到key的节点endl;elsecout不存在key的节点endl;else if(keydata.key)Searc

4、hBST(t-lchild,key);elseSearchBST(t-rchild,key);template void BSTree:InsertBST(bitree *(&t),Node e)/元素插入STlen=e;len+; p=t; while(p)if(p-data.key=e.key)cout二叉排序树中已经存在值为:e.key的节点n;exit(1);f=p;if(e.keydata.key)p=p-lchild;elsep=p-rchild;p=new bitree;p-data=e;p-lchild=p-rchild=NULL;if(t=NULL)t=p;elseif(e.

5、keydata.key)f-lchild=p;elsef-rchild=p;template int BSTree:DeleteBST(bitree *(&t),T key)/ 元素删除if(!t) coutdata.key)return Delete(t);else if(keydata.key) return DeleteBST(t-lchild,key);elsereturn DeleteBST(t-rchild,key);template int BSTree:Delete(bitree *(&p)bitree *q,*s;if(!p-rchild)q=p;p=p-lchild;del

6、ete q;cout成功删除lchild)q=p;p=p-rchild;delete q;cout成功删除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 void BSTree:DeleteElem(T key)/顺序表元素删除 for(int i=0;ilen & STi.key!=key;i+);if(ilen)for(int j=i+1;jlen;

7、j+)STi=STj;len-;template void BSTree:InDisplay(bitree *t)/中序遍历输出if(t!=NULL)InDisplay(t-lchild);coutdata.keyrchild);template void BSTree:Display()/输出查找表中的数据元素cout查找表中的数据元素关键字依次为:n;for(int i=0;ilen;i+)coutSTi.key ;coutendl;void main()int m,l,i;BSTree a;do cout- 二叉排序树的基本操作-endl; cout- 1. 创建查找表 -n -2. 插

8、入元素-n - 3. 删除元素 -n - 4. 查找元素 -n - 5. 中序遍历二叉排序树输出-n - 6. 查找表输出 -n - 7. 退出 -n m; if(m=1)Node e;coutl;cout输入l个不同的数据元素n;for(i=0;ie.key;a.InsertBST(a.t,e); else if(m=2)Node e;coute.key;a.InsertBST(a.t,e); else if(m=3)T key;coutkey;a.DeleteBST(a.t,key);a.DeleteElem(key); else if(m=4)T key;coutkey;a.SearchBST(a.t,key);else if(m=5)cout中序遍历的输出结果为:n;a.InDisplay(a.t);coutendl;else if(m=6)cout二叉排序树输出:n;a.Display();coutendl;else if(m=7)cout结束运行!n;elsecout输入代码非法,代码在0-7之间,请重新输入endl;/coutendl;cout请继续选择操作endl;while(m!=7);-第 7 页-