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