二叉树实现

#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)
 {
  cout<<"in copy structure"<  BSTNode* head=tree.getroot();
        root=new BSTNode(head->element);
  root->left=copyBST(head->left);
  root->right=copyBST(right->right);
 }
 void visit(BSTNode* p)
 {
  cout<element<<",";
 }
 BSTNode* copyBST(BSTNode* node)
 {
 if(node!=NULL)
  {
         BSTNode* temp=new BSTNode(node->element);
   temp->left=copyBST(node->left);
   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 <<(ostream& out,BSTNode& node);
 friend istream& 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;
   }

}
cout<}

 

 

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

 

/////////////////////////////////////////////////////////////
//二叉树后序遍历
/////////////////////////////////////////////////////////////
template
void BST::postorder()
{
stack*> pool;
BSTNode* pre=root;
BSTNode* head=root;
while(head!=NULL)
{
for(;head->left!=NULL;head=head->left) //左子树入栈
{
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;                        //访问右子树
}
cout<}

 

/////////////////////////////////////////////////////////////
//二叉树结点加入
/////////////////////////////////////////////////////////////
template
void BST::insert(const T& e)
{
 BSTNode* temp=findnode(e);
 if(temp==NULL)
 {
      BSTNode* p=root;
   BSTNode* pre=0;
   while(p!=0)
   {
          pre=p;
    if(p->element     p=p->right;
    else
     p=p->left;
   }
   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
  cout<<"node already exist"<}

/////////////////////////////////////////////////////////////
//二叉树结点查找
/////////////////////////////////////////////////////////////
template
BSTNode* BST::findnode(const T& e)
 {
      BSTNode* p=root;
   stack*> s;
   while(p!=NULL||!s.empty())
   {
    while(p!=NULL)
   {
    if(p->element==e)
     return p;
    s.push(p);
    p=p->left;
      }
   if(!s.empty())
   {
    p=s.top();
    s.pop();
    p=p->right;
   }
   }
   return NULL;
 }

/////////////////////////////////////////////////////////////
//二叉树结点删除
/////////////////////////////////////////////////////////////
template
void BST::remove(BSTNode*& node)
{
BSTNode* temp=node;
if(node!=0)
{
if(!node->right)
{
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<<"key "< else cout<<"the tree is empty"< }

}

 

/////////////////////////////////////////////////////////////
//打印二叉树结点
/////////////////////////////////////////////////////////////
template
void BST::printData(T data,int level ){
for( int i = 0; i < level; i++ ){
printf( "   ");
}
cout<}

 

/////////////////////////////////////////////////////////////
//打印二叉树结构
/////////////////////////////////////////////////////////////
template
void BST::printTree(BSTNode* node,int level){
if( node == NULL ) return;
if( node->right ) {
printTree( node->right, level + 1 );
}
printData( node->element, level );
if( node->left ){
printTree( node->left, level + 1 );
}
}

/////////////////////////////////////////////////////////////
//构造二叉树
/////////////////////////////////////////////////////////////
template
void BST::CreateNode(BSTNode* node,istream& in)
{
if(node!=NULL)
{
 cout<<"please input the left node of "<element< T e;
 in>>e;
 if(e!=T())
 {
    BSTNode* left=new BSTNode(0,0,e);
 node->left=left;
 CreateNode(left,in);
 }
 cout<<"please input the right node of "<element< in>>e;
 if(e!=T())
 {
    BSTNode* right=new BSTNode(0,0,e);
 node->right=right;
 CreateNode(right,in);
 }
}
else
{
 cout<<"please input root"< T e;
    in>>e;
 root=new BSTNode(0,0,e);
 CreateNode(root,in);
}
}

/////////////////////////////////////////////////////////////
//返回二叉树根结点
/////////////////////////////////////////////////////////////
template
BSTNode* BST::getroot()
{
 return root;
}

/////////////////////////////////////////////////////////////
//输入二叉树
/////////////////////////////////////////////////////////////
template
void BST::Input(istream& in)
{
cout<<"please input the tree node"<CreateNode(root,in);
}

/////////////////////////////////////////////////////////////
//输出二叉树
/////////////////////////////////////////////////////////////
template
void BST::Output(ostream& out)
{
out<<"the BST tree is as follows:"<printTree(root,0);
}

/////////////////////////////////////////////////////////////
//重载二叉树<<
/////////////////////////////////////////////////////////////
template
ostream& operator << (ostream& out,BST& node)
{
node.Output(out);
return out;
}

/////////////////////////////////////////////////////////////
//重载二叉树>>
/////////////////////////////////////////////////////////////
template
istream& operator >> (istream& in,BST& node)
{
node.Input(in);
return in;
}

int main()
{
 BST x=BST();
 cin>>x;
 cout< system("pause");
}