二叉树的实现

#include "iostream.h" class BSTNode{ public: BSTNode(){ left=right=0; } BSTNode(int el,BSTNode* l=0,BSTNode* r=0){ key=el;left=l;right=r; } int key; BSTNode*left,*right; }; class BST{ public: BST() { root=0; } bool isEmpty() { return root==0; } void inorder(){ inorder(root); } void clean() { root=0; } BSTNode* search(int &el){ return search(root,el); } void insert(int el); void deleteByMerging(BSTNode*&); void findAndDeleteByMerging(int &); BSTNode* root; BSTNode*search(BSTNode*,int &); void inorder(BSTNode*); }; void BST::inorder(BSTNode* p) { if(p!=0) { inorder(p->left); cout<<p->key<<" "; inorder(p->right); } } void BST::insert(int el){ BSTNode* p=root,*prev=0; while(p!=0){ prev=p; if(p->key<el) p=p->right; else p=p->left; } if(root==0) root=new BSTNode(el); else if(prev->key<el) prev->right=new BSTNode(el); else prev->left=new BSTNode(el); } BSTNode* BST::search(BSTNode* p,int &el) { while(p!=0) { if(p->key==el) return p; else if(p->key<el) p=p->right; else p=p->left; } return 0; } void BST::deleteByMerging(BSTNode* &node){ BSTNode*tmp=node; if(node!=0){ if(!node->right) node=node->left; else if(node->left==0) node=node->right; else{ tmp=node->left; while(tmp->right==0) tmp=tmp->right; tmp->right=node->right; tmp=node; node=node->left; } delete tmp; } } void BST::findAndDeleteByMerging(int &el){ BSTNode *node=root,*prev=0; while(node!=0){ if(node->key==el) break; prev=node; if(node->key<el) node=node->right; else node=node->left; } if(node!=0&&node->key==el) if(node==root) deleteByMerging(root); else if(prev->left==node) deleteByMerging(prev->left); else deleteByMerging(prev->right); else if(root!=0) cout<<"key"<<el<<"is not in the tree\n"; else cout<<"the tree is empty\n"; } int main() { cout<<"************************请选择你需要执行的操作****************************"<<endl<<endl<<endl; cout<<"1.建立树"<<" 2.显示树 "<<" 3.插入数 "<<"4.寻找数 "<<"5.删除数"<<" 6.清空树"<<endl; cout<<endl; BST tree; int num; int n; int ch; int i; while(1) { cin>>ch; switch(ch) { case 1: cout<<"请输入要建立的树的节点数："<<endl; cin>>n; for(i=0;i<n;i++) { cout<<"请输入第"<<i+1<<"个数："<<endl; cin>>num; tree.insert(num); } cout<<"----------------------------------------"<<endl; break; case 2: if(!tree.isEmpty()) { cout<<"从小到大显示如下："<<endl; tree.inorder(); cout<<endl; } else cout<<"二叉树为空!"<<endl; cout<<"----------------------------------------"<<endl; break; case 3: cout<<"请插入一个数: "<<endl; cin>>num; tree.insert(num); cout<<"----------------------------------------"<<endl; break; case 4: cout<<"请输入你要找的数: "<<endl; cin>>num; if(tree.search(num)==0) { cout<<"没有在树中!"<<endl; } else { cout<<"确实在树中!"<<endl; } cout<<"----------------------------------------"<<endl; break; case 5: cout<<"请输入你要删除的数: "<<endl; cin>>num; if(tree.search(num)==0) cout<<"错误：此书没在树中"<<endl; else { tree.findAndDeleteByMerging(num); cout<<"成功删除!"<<endl; } cout<<"----------------------------------------"<<endl; break; case 6: tree.clean(); cout<<"----------------------------------------"<<endl; break; default: break; } } return 0; }