二叉树实现

#include #include #include using namespace std;

/ //普通二叉树结点结构 / template struct BSTNode { BSTNode *left,*right; T element; BSTNode(BSTNode* x=0,BSTNode* y=0,T e=T()) { left=x; right=y; element=e; } };

/ //普通二叉树类 / template class BST { public:  BST(){root=NULL;}  BST(BST& tree)  {   coutright=copyBST(right->right);  }  void visit(BSTNode* p)  {   coutleft);    temp->right=copyBST(node->right);    return temp;   }   return NULL;  }  void preorder();  void midorder();  void postorder();  BSTNode* getroot();     void insert(const T& e);     BSTNode* findnode(const T& e);     void remove(BSTNode*& node);     void remove(const T& e);  void printData( T data, int level );     void printTree( BSTNode* node, int level );     void CreateNode(BSTNode* node,istream& in);  ~BST(){delete root;}  void Input(istream& in);  void Output(ostream& out);

private:  BSTNode* root;  friend ostream& operator (istream& in,BSTNode& node);

};

/ //二叉树先序遍历 / template void BST::preorder() { stack pool; BSTNode* head=root; while(!pool.empty()||head!=NULL) {    while(head!=NULL)    {     visit(head);     pool.push(head);     head=head->left;    }    if(!pool.empty())    {       head=pool.top();     pool.pop();     head=head->right;    }

} coutright;  } } coutleft) //左子树入栈 { pool.push(head);                          } while(head!=NULL&&(head->right==0||head->right==pre))  //访问左子树结点，或根结点(右子树访问完毕) { visit(head);                                          pre=head; if(pool.empty()) return; head=pool.top(); pool.pop(); } pool.push(head);                          //压入根结点 head=head->right;                        //访问右子树 } coutleft;    }    if(root==0)     root=new BSTNode(0,0,e);    else    {     if((pre->element)>e)      pre->left=new BSTNode(0,0,e);     else            pre->right=new BSTNode(0,0,e);

   }  }  else   coutright) { node=node->left; } else if(!node->left) { node=node->right; } else { temp=node->right; while(temp->left!=0) temp=temp->left; temp->left=node->left; temp=node; node=node->right; } delete temp; } }

template void BST::remove(const T& e) {  BSTNode* pre=findpre(e);  BSTNode* node=findnode(e);  if(node!=NULL)  {  if(pre->left==node)   remove(pre->left);  else if(pre->right==node)   remove(pre->right);  else if(root!=0)   cout