#include<iostream> #include<cstdio> #include<stack> #include<vector> #include<cstdlib> #include<cstdio> #include<string> #include<climits> using namespace std; template<typename elem> class binNode { public: elem val; binNode<elem> *left,*right; binNode(elem v,binNode *leftChild,binNode *rightChild) :val(v),left(leftChild),right(rightChild){} binNode(){} }; template<typename elem> class binTree { private: int maxheight; binNode<elem> *root; stack<binNode<elem>*> sta; size_t size; void make_empty(binNode<elem> *&Sroot) { if(Sroot!=NULL) { make_empty(Sroot->left); make_empty(Sroot->right); delete Sroot; } Sroot=NULL; } binNode<elem>* &findMin(binNode<elem>* rt) { if(rt==NULL) { binNode<elem>* tem=NULL; return tem; } while(rt->left!=NULL) rt=rt->left; return rt; } binNode<elem>* &findMax(binNode<elem>* rt) { if(rt==NULL) { binNode<elem>* tem=NULL; return tem; } while(rt->right!=NULL) rt=rt->right; return rt; } void remove(const elem& n,binNode<elem>* &rt) { if(rt==NULL) return ; else if(n<rt->val) remove(n,rt->left); else if(n>rt->val) remove(n,rt->right); else if(rt->left!=NULL&&rt->right!=NULL) { if(rt->right->left==NULL) { binNode<elem> *temp=rt->right; rt->val=rt->right->val; rt->right=rt->right->right; delete temp; temp=NULL; } else { binNode<elem>* temp=rt->right; while(temp->left->left!=NULL) temp=temp->left; rt->val=temp->left->val; binNode<elem>* mid=temp->left; temp->left=mid->right; delete mid; mid=NULL; } } else { binNode<elem> *old=rt; rt=(rt->left!=NULL) ? rt->left:rt->right; delete old; } } void dfs(binNode<elem>* rt,int cnt)//用于求树高 { if(cnt>maxheight) maxheight=cnt; if(rt->left!=NULL) dfs(rt->left,cnt+1); if(rt->right!=NULL) dfs(rt->right,cnt+1); } public: binTree() { root=NULL; size=0; } ~binTree() { clear(); } void insert(const elem& n)//插入节点 { binNode<elem>* tem=root; if(root==NULL) { root=new binNode<elem>(n,NULL,NULL); return ; } while(1) { if(n==tem->val) return ; else if(n>tem->val) { if(tem->right!=NULL) tem=tem->right; else { tem->right=new binNode<elem>(n,NULL,NULL); size++;break;} } else { if(tem->left!=NULL) tem=tem->left; else {tem->left=new binNode<elem>(n,NULL,NULL);size++;break;} } } } void clear()//清空树 { make_empty(root); size=0; } bool contains(const elem& n)//判断是否包含某个数 { if(root==NULL) return false; binNode<elem>* tem=root; while(tem!=NULL) { if(tem->val==n) return true; else if(tem->val>n) tem=tem->left; else tem=tem->right; } return false; } void remove(const elem&n)//移除一个节点 { remove(n,root); } void travelsal()//中序遍历 { if(root==NULL){ cout<<"empty tree!"<<endl; return;} binNode<elem> *cur=root; while(1) { if(cur==NULL) { if(sta.empty()) break; binNode<elem> *top=sta.top(); sta.pop(); cout<<top->val<<' '; cur=top->right; } else { sta.push(cur); cur=cur->left; } } } elem maxElem()//返回最大值 { binNode<elem>* tem=findMax(root); if(tem==NULL) return INT_MAX; else return tem->val; } elem minElem()//返回最小值 { binNode<elem>* tem=findMin(root); if(tem==NULL) return INT_MIN; else return tem->val; } int height()//返回树高 { maxheight=-1; dfs(root,1); return maxheight; } int getSize()//返回数中节点数 { return size; } }; binTree<int> big; int tt[10]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>tt[i]; big.insert(tt[i]); } big.travelsal(); big.remove(tt[0]); big.travelsal(); }