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

《数据结构二叉排序树操作源代码.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构二叉排序树操作源代码：#includeusingnamespacestd;#defineTRUE1;#defineFALSE0;typedefintT;constmaxsize=50;templatestructNode{Tkey;/*.....*/};templatestructbitree{Nodedata;bitree*lchild;bitree*rchild;};templateclassBSTree{public:Node*ST;intlen;//无素个数bit

2、ree*t;//根指针bitree*f;//根指针的双亲指针bitree*p;//指向查找路径上最后访问的节点BSTree();//构造函数~BSTree();//析构函数voidSearchBST(bitree*t,Tkey);//二叉排序树查找voidInsertBST(bitree*(&t),Nodee);//元素插入intDeleteBST(bitree*(&t),Tkey);//二叉排序树中元素删除intDelete(bitree*(&p));//voidDeleteElem(Tkey);//查找表元素删除voi

3、dInDisplay(bitree*t);//中序遍历二叉排序树voidDisplay();//查找表显示};templateBSTree::BSTree(){//构造函数，初始化查找表ST=newNode[maxsize];//顺序存放查找表len=0;t=NULL;//查找树初始化}templateBSTree::~BSTree(){//析构函数，销毁查找表delete[]ST;len=0;deletet;cout<<"成功销毁二叉排序树";}templatevoidBSTree::S

4、earchBST(bitree*t,Tkey){//元素查找if(t==NULL

5、

6、key==t->data.key){if(key==t->data.key)cout<<"找到"<data.key)SearchBST(t->lchild,key);elseSearchBST(t->rchild,key);}templatevoidBSTree::InsertBST(bitree*(&t),Node

7、e){//元素插入ST[len]=e;len++;p=t;while(p){if(p->data.key==e.key){cout<<"二叉排序树中已经存在值为:"<data.key)p=p->lchild;elsep=p->rchild;p=newbitree;p->data=e;p->lchild=p->rchild=NULL;if(t==NULL)t=p;else{if(e.keydata.key)f->lchild=p;elsef->rchild=p;}}}templ

8、ateintBSTree::DeleteBST(bitree*(&t),Tkey){//元素删除if(!t){cout<<"二叉树为空,无法删除";returnFALSE;}else{if(key==t->data.key)returnDelete(t);elseif(keydata.key)returnDeleteBST(t->lchild,key);elsereturnDeleteBST(t->rchild,key);}}templateintBSTree::Delete(bitree*(&p)){

9、bitree*q,*s;if(!p->rchild){q=p;p=p->lchild;deleteq;cout<<"成功删除"<lchild){q=p;p=p->rchild;deleteq;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;deletes;cout