BSTREE
BST.h
#pragma once template<class Type>//友元类声明 class BSTree;//友元类声明 template<class Type> class BSTNode//自定义的结点类型及特征 { friend class BSTree<Type>;//友元 public: BSTNode():data(Type()),leftChild(NULL),rightChild(NULL)//定义类型 {} BSTNode(Type d, BSTNode<Type> *left=NULL, BSTNode<Type> *right=NULL)//初始化 : data(d), leftChild(left),rightChild(right) {} ~BSTNode() {} private: Type data; BSTNode *leftChild; BSTNode *rightChild; }; template<class Type> class BSTree//二叉排序树 { public: BSTree():root(NULL) {} BSTree(Type *ar, int n) : root(NULL) { for(int i=0; i<n; ++i) { Insert(ar[i]);//插入元素，即建立二叉树 } } ~BSTree()//析构 { MakeEmpty(); } public: bool Insert(const Type &x)//插入声明 { return Insert(root, x); } Type& Max()//最大的数 {return Max(root);} //const Type& Max()const;//常方法与上面的有区别，其函数必须用const Type& Min()//最小数 {return Min(root);} //const Type& Min()const; BSTNode<Type>* Search(const Type &key)const//寻找某个关键数 {return Search(root, key);} BSTNode<Type>* Parent(const Type &key)const//寻找某个关键数的父结点 {return Parent(root, key);} void SortPrint()const//打印出各结点树 {SortPrint(root);} bool Equal(const BSTree<Type> &bst)const//判断两个树，是否完全相等，是否相同 {return Equal(root, bst.root);} //bst1.Copy(bst); void Copy(const BSTree<Type> &bst)//复制一个树 {root = Copy(bst.root);} /// bool Remove(const Type &key)//删除某个结点 {return Remove(root, key);} protected: void MakeEmpty() {MakeEmpty(root);} protected: bool Remove(BSTNode<Type> *&t, const Type &key) { if(t == NULL) return false; if(key < t->data) Remove(t->leftChild, key); else if(key > t->data) Remove(t->rightChild, key); else { if(t->leftChild==NULL && t->rightChild==NULL) { delete t; t = NULL; } else if(t->leftChild!=NULL && t->rightChild==NULL) { BSTNode<Type> *p = t; t = p->leftChild; delete p; } else if(t->leftChild==NULL && t->rightChild!=NULL) { BSTNode<Type> *p = t; t = p->rightChild; delete p; } else { BSTNode<Type> *p = t->rightChild; while(p->leftChild != NULL) p = p->leftChild; t->data = p->data; Remove(t->rightChild, p->data); /* BSTNode<Type> *p = t->leftChild; while(p->rightChild != NULL) p = p->rightChild; t->data = p->data; Remove(t->leftChild, p->data); */ } return true; } } void MakeEmpty(BSTNode<Type> *&t) { if(t != NULL) { MakeEmpty(t->leftChild); MakeEmpty(t->rightChild); delete t; } } bool Equal(BSTNode<Type> *t1, BSTNode<Type> *t2)const { if(t1==NULL && t2==NULL) return true; if(t1!=NULL && t2!=NULL &&t1->data==t2->data && Equal(t1->leftChild, t2->leftChild) && Equal(t1->rightChild, t2->rightChild)) return true; return false; } BSTNode<Type>* Copy(BSTNode<Type> *t) { if(t == NULL) return NULL; BSTNode<Type> *s = new BSTNode<Type>(t->data); s->leftChild = Copy(t->leftChild); s->rightChild = Copy(t->rightChild); return s; } void SortPrint(BSTNode<Type> *t)const { if(t != NULL) { SortPrint(t->leftChild); cout<<t->data<<" "; SortPrint(t->rightChild); } } BSTNode<Type>* Parent(BSTNode<Type> *t, const Type &key)const { BSTNode<Type> *p = Search(t, key); if(p==NULL || t==NULL || key==t->data) return NULL; if(t->leftChild==p || t->rightChild==p) return t; if(key < t->data) Parent(t->leftChild, key); else if(key > t->data) Parent(t->rightChild, key); } BSTNode<Type>* Search(BSTNode<Type> *t, const Type &key)const { if(t == NULL) return NULL; if(t->data == key) return t; else if(key < t->data) Search(t->leftChild, key); else Search(t->rightChild, key); } Type& Max(BSTNode<Type> *t) { BSTNode<Type> *p = t; while(p->rightChild != NULL) p = p->rightChild; return p->data; } Type& Min(BSTNode<Type> *t) { BSTNode<Type> *p = t; while(p->leftChild != NULL) p = p->leftChild; return p->data; } bool Insert(BSTNode<Type> *&t, const Type &x) { if(t == NULL) { t = new BSTNode<Type>(x); return true; } else if(x < t->data) Insert(t->leftChild, x); else if(x > t->data) Insert(t->rightChild, x); else return false; } private: BSTNode<Type> *root; }; main.cpp #include<iostream> //#include<vld.h> using namespace std; #include"BST.h" void main() { int ar[] = {53, 78, 65, 17, 87, 9, 81, 45, 23}; int n = sizeof(ar) / sizeof(int); BSTree<int> bst(ar, n); bst.Remove(78);//检测删除 } /* void main() { int ar[] = {53, 78, 65, 17, 87, 9, 81, 45, 23}; int n = sizeof(ar) / sizeof(int); BSTree<int> bst(ar, n); cout<<"Max Value = "<<bst.Max()<<endl;//输出最大值 cout<<"Min Value = "<<bst.Min()<<endl;//输出最小值 BSTNode<int> *p = bst.Search(17);//寻找17这个数，有则返回，没有则返回为空 BSTNode<int> *pa = bst.Parent(23);//找23的父结点 bst.SortPrint();//打印排序后的数 cout<<endl; BSTree<int> bst1; bst1.Copy(bst);//复制 bool flag = bst.Equal(bst1);//判断两树是否相等，相等的话返回标志flag=1 cout<<"flag = "<<flag<<endl; return; }*/ /* void main()//建立二叉排序树 { int ar[] = {53, 78, 65, 17, 87, 9, 81, 45, 23}; int n = sizeof(ar) / sizeof(int); BSTree<int> bst; for(int i=0; i<n; ++i) { bst.Insert(ar[i]); } return; }*/
