binarytree.h

大二半年的数据结构上机实验。包括链表

#ifndef _BinaryTree_H_
#define _BinaryTree_H_
#include"iostream.h"
#include"stdlib.h"
struct NodeType
{int data;
 NodeType *left,*right;
};

template<class T>
class BinaryTree{
    private:
      NodeType *root;
    public:
      BinaryTree() {root=NULL;};
       ~BinaryTree(void) {};
       bool IsEmpty() const {return((root)?false:true);};
       bool Root() const;
       void PreOrder(NodeType *p);
       void InOrder(NodeType *p);
       void PostOrder(NodeType *p);
       NodeType *Creat();
       void MakeTree();
       void Destroy(NodeType *p);
       int Height(NodeType *p);
       void Preorderswitch(NodeType *p);
       NodeType *Getroot(){return root;};
};
 #endif
 
template<class T>
void BinaryTree<T>::MakeTree()
{cout<<"请按照树的先序遍历输入数据:"<<endl;
 cout<<"将节点的空孩子用0输入"<<endl;
 root=Creat();
}

template<class T>
bool BinaryTree<T>::Root() const
{T x;
 if(root) 
  {x=root->data;
   cout<<"二叉树的根是："<<x<<endl;
   return true;}
 else
 cout<<"此二叉树为空"<<endl;  
 return false;
}

template<class T>
void BinaryTree<T>::Destroy(NodeType *p)
{if(p!=NULL)
    {Destroy(p->left);
     Destroy(p->right);
     delete p;
     p=NULL;
     }
}

template<class T>
void BinaryTree<T>::PreOrder(NodeType *p)
{if(p!=NULL)
  {cout<<p->data<<","<<endl;
   PreOrder(p->left);
   PreOrder(p->right);
  }
}

template<class T>
void BinaryTree<T>::InOrder(NodeType *p)
{ if(p!=NULL)
  {InOrder(p->left);
   cout<<p->data<<","<<endl;
   InOrder(p->right);
  }
}

template<class T>
void BinaryTree<T>::PostOrder(NodeType *p)
{ if(p!=NULL)
  {PostOrder(p->left);
   PostOrder(p->right);
   cout<<p->data<<","<<endl;
  }
}


template<class T>
int BinaryTree<T>::Height(NodeType *p)
{int hl,hr;
 if(p==NULL) return 0;
 else
  {hl=Height(p->left);
   hr=Height(p->right);
   return 1+(hl>hr?hl:hr);
  }
}

template<class T>
void BinaryTree<T>::Preorderswitch(NodeType *p)
{if(p!=NULL)
  {NodeType *r; r=p->left;
    p->left=p->right; p->right=r;
    Preorderswitch(p->left);
    Preorderswitch(p->right);
  }
}

template<class T>
NodeType *BinaryTree<T>::Creat()
{NodeType *p; T x;
   cout<<"\n 请输入数据："<<endl;
   cin>>x;
   if(x==0) p==NULL;
   else
     {p=new NodeType;
      p->data=x;
      p->left=Creat();
      p->right=Creat();
     }
   return p;
}