求个二叉排序树查找的递归算法

#include<iostream> #include<string> #include<cstring> using namespace std; class BinaryTreeNode {public: string data; int w; BinaryTreeNode *leftchild; BinaryTreeNode *rightchild; BinaryTreeNode *parent; int pos[50]; BinaryTreeNode(string a,int postion) { data=a; w=1; leftchild=NULL; rightchild=NULL; parent=NULL; pos[0]=postion; } }; class BSTree {public: BinaryTreeNode *root; BSTree(){root=NULL;} void Insert(string a,int postion); void Delete(string key); BinaryTreeNode *Search(string key,BinaryTreeNode*& pr,BinaryTreeNode *&parent); void InOrder(BinaryTreeNode *&root); void PreOrder(BinaryTreeNode *&root); }; void BSTree::InOrder(BinaryTreeNode *&root) { if(root) { InOrder(root->leftchild); cout<<root->data; cout<<" "<<root->w<<endl; InOrder(root->rightchild); } } void BSTree::PreOrder(BinaryTreeNode*& root) { if(root) { cout<<root->data; cout<<" "<<root->w<<endl; PreOrder(root->leftchild); PreOrder(root->rightchild); } } BinaryTreeNode *BSTree::Search(string key,BinaryTreeNode*& pr,BinaryTreeNode*& parents) { BinaryTreeNode *p=root; pr=root; while(p) { parents=p; if(key<p->data) { pr=p; p=p->leftchild; } else if(key>p->data) { pr=p; p=p->rightchild; } else return p; } return NULL; } void BSTree::Insert(string a,int postion) { BinaryTreeNode *pr,*p,*pp=NULL; p=Search(a,pr,pp); if(p!=NULL) { p->w++; p->pos[p->w-1]=postion; return; } BinaryTreeNode *r=new BinaryTreeNode(a,postion); if(!root) root=r; else if(a<pp->data) pp->leftchild=r; else pp->rightchild=r; } void BSTree::Delete(string key) { BinaryTreeNode *p,*pr,*pp; p=Search(key,pp,pr); if(p==NULL) return; if(p->leftchild&&p->rightchild) { BinaryTreeNode *s=p->rightchild,*ps=p; while(s->leftchild) { ps=s; s=s->leftchild; } p->data=s->data; p->w=s->w; for(int i=0;i<s->w;i++) { p->pos[i]=s->pos[i]; } pp=ps; p=s; } if(p->leftchild) { if(pp->leftchild==p) { pp->leftchild=p->leftchild; p->leftchild->parent=pp; } else { pp->rightchild=p->leftchild; p->leftchild->parent=pp; } } else if(p->rightchild) { if(pp->leftchild