Question

二叉排序树的实现(C++) 用顺序和二叉链表作存储结构

用顺序和二叉链表作存储结构 以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; 对二叉排序树T作中序遍历,输出结果; 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息"无x";

Answer 1

2 代码： 1 ）二叉排序树： #include"BSTreeNode.h" #include"seqstack.h" #define Max(x1,x2) (x1>x2?x1:x2) //返回两个数中的最大者 #include <iostream> using namespace std; template <class Type> class BSTree { private: //void destory(BSTreeNode<Type> *p);//删除以p为根的二叉树 void InOrder(BSTreeNode<Type> *r);//私有函数：此算法按照中序次序遍历二叉树 void PostOrder(BSTreeNode<Type> *r);//私有函数：此算法按照后序次序遍历二叉树 int Depth(const BSTreeNode<Type> *r); //私有函数：此算法计算二叉树的深度 int LeafSize(const BSTreeNode<Type> *r); //私有函数：此算法计算二叉树的叶子结点个数 //void CreatPreThreed(BSTreeNode<Type> *&r); BSTreeNode<Type>*Find(const Type &k,BSTreeNode<Type>*p)const; void Insert(const Type &x,BSTreeNode<Type>*&p); void Delete(const Type &k,BSTreeNode<Type>*&p); BSTreeNode<Type>*& Min(BSTreeNode<Type>*&p); BSTreeNode<Type> *root; public: BSTree():root(NULL){} BSTreeNode<Type> *Root(){return root;} int Depth(); //计算二叉树的深度 int LeafSize(); //计算二叉树的叶子结点个数 void PreOrder();//用栈先序遍历二叉树 void CreatPreThreed(){CreatPreThreed(root);} void InOrder(); void PostOrder(); BSTreeNode<Type> *Find(const Type &k)const{return Find(k,root);} //BSTreeNode<Type>*& Min(){Min(BSTreeNode<Type>*&p);}; //Type Max(); void Insret(const Type &x){Insert(x,root);} void Delete(const Type &k){Delete(k,root);} void CreatBSTree(); }; template <class Type> void BSTree<Type>::InOrder(BSTreeNode<Type> *r) { if(r!=NULL) { InOrder(r->GetLeftChild()); cout<<r->GetData()<<'\t'; InOrder(r->GetRightChild()); } } template <class Type> void BSTree<Type>::PostOrder(BSTreeNode<Type>*r) { if(r!=NULL) { PostOrder(r->GetLeftChild()); PostOrder(r->GetRightChild()); cout<<r->GetData()<<'\t'; } } template <class Type> int BSTree<Type>::LeafSize() { return LeafSize(root); } template <class Type> int BSTree<Type>::LeafSize(const BSTreeNode<Type> * t) { if(t==NULL) return 0; //递归结束条件：空树叶子结点个数为 else if(t->leftChild == NULL && t->rightChild == NULL) return 1; else return LeafSize(t->leftChild)+LeafSize(t->rightChild); } template <class Type> int BSTree<Type>::Depth() { return Depth(root); } template <class Type> int BSTree<Type>::Depth(const BSTreeNode<Type>* t) { if(t==NULL) return 0; //递归结束条件：空树深度为 return 1+Max(Depth(t->leftChild),Depth(t->rightChild)); } template<class Type> void BSTree<Type>::PreOrder() { seqstack<BSTreeNode<Type> *> s(50); if(root==NULL) cout<<"二叉树为空！"<<endl; s.push(root); cout<<root->data<<" "; BSTreeNode<Type> *p=root->GetLeftChild(); do { if(p!=NULL) { cout<<p->GetData()<<" "; s.push(p); p=p->GetLeftChild(); } else if(s.empty()!=1) { p=s.pop(); p=p->GetRightChild(); } }while(s.empty()!=1||p!=NULL); } /*template<class Type> void BSTree<Type>::CreatPreThreed(BSTreeNode<Type> *&r) { Type ch; cin>>ch; if(ch=='#')return; r=new BinTreeNode<Type>(ch,NULL,NULL); CreatPreThreed(r->leftChild); CreatPreThreed(r->rightChild); }*/ template <class Type> void BSTree<Type>::InOrder() { InOrder(root); } template <class Type> void BSTree<Type>::PostOrder() { PostOrder(root); }/* template<class Type> BSTreeNode<Type>* BSTree<Type>::Find(const Type &k,BSTree<Type>*p)const { if(p==NULL) return NULL; else if（k<p->data） return Find(k,p->leftChild); else if(k>p->data) return Find(k,p->rightChild); else return p; }*/ template<class Type> BSTreeNode<Type> *BSTree<Type>::Find(const Type &k,BSTreeNode<Type>*p)const//在p为根的二叉排序树上进行查找的迭代算法 { BSTreeNode<Type>*temp=p; if(p!=NULL) { while(temp!=NULL) { if(temp->data==k) return temp;//查找成功 if(temp->data<k) temp=temp->rightChild;//查找右子树 else temp=temp->leftChild;//查找左子树 } } return temp;//查找失败 } template<class Type> void BSTree<Type>::Insert(const Type &x,BSTreeNode<Type>*&p)//在p为根的二叉排序树上插入结点的递归算法 { if(p==NULL)//空二叉树 p=new BSTreeNode<Type>(x);//创建数据元素x的结点 else if(x<p->data) Insert(x,p->leftChild);//在左子树插入 else if(x>p->data) Insert(x,p->rightChild);//在右子树插入 else //结点x存在 { cout<<"已经存在该节点插入失败"<<endl; exit(1); } } template<class Type>void BSTree<Type>::Delete(const Type &k,BSTreeNode<Type>*&p) { BSTreeNode<Type>*temp; if(k<p->data) Delete(k,p->leftChild);//若p的关键字大于k，则在p的左子树删除 else if(k>p->data) //delete(k,p->rightChild); Delete(k,p->rightChild);//若p的关键字小于k，则在p的右子树删除 else if(p->leftChild!=NULL&&p->rightChild!=NULL) { /* temp=Min(p->rightChild); p->data=temp->data; delete(p->data,temp); */ BSTreeNode<Type> *&temp1=Min(p->rightChild); p->data=temp1->data; Delete(p->data,temp1); //注意这里和你原来的比较是Delete而非delete } else { temp=p; if(p->leftChild==NULL) p=p->rightChild; else if(p->rightChild==NULL) p=p->leftChild; delete temp; } } template<class Type>void BSTree<Type>::CreatBSTree() { int i(0); cout<<'\n'; Type ch; while(ch!=-1) { cout<<"第"<<i<<"个节点"; cin>>ch; if(ch!=-1) { Insert(ch,root); i++; } else break; } } //template <class Type> template<class Type>BSTreeNode<Type>*& BSTree<Type>::Min(BSTreeNode<Type> *&p) { /* BSTreeNode<Type>*&q; while(p!=NULL) { q=p; p=p->GetLeftChild(); } */ while (p->leftChild!=NULL) p=p->leftChild; return p; }