
#include<iostream.h>
#include"SeqQueue.cpp"
template<class Type>
struct BinTreeNode{
Type data;
BinTreeNode<Type> * leftChild, * rightChild;
BinTreeNode():leftChild(NULL),rightChild(NULL){}
BinTreeNode(Type x,BinTreeNode<Type> * l = NULL,BinTreeNode<Type> * r = NULL)
:data(x),leftChild(l),rightChild(r){}
};
template<class Type>
class BinaryTree{
public:
BinaryTree():root(NULL){}
BinaryTree(Type value):ReValue(value),root(NULL){}
~BinaryTree(){destory(root);}
bool IsEmpty(){return(root==NULL)?true:false;}
BinTreeNode<Type>*Parent(BinTreeNode<Type>*current){return(root==NULL||root==current)?NULL:Parent(root,current);}//返回父节点
BinTreeNode<Type>*LeftChild(BinTreeNode<Type>*current){return(current!=NULL)?current->leftChild:NULL;}//返回左子女
BinTreeNode<Type>*RightChild(BinTreeNode<Type>*current){return(current!=NULL)?current->rightChild:NULL;}//返回右子女
int Height(){return Size(root);}
BinTreeNode<Type>*getRoot()const{return root;}
void preOrder(void(*visit)(BinTreeNode<Type>*p)){PreOrder(root,visit);}//前序
void inOrder(void(*visit)(BinTreeNode<Type>*p)){InOrder(root,visit);}//中序遍历
void postOrder(void(*visit)(BinTreeNode<Type>*p)){PostOrder(root,visit);}//后续遍历
void levelOrder(void(*visit)(BinTreeNode<Type>*p));//层序
// int Insert(const Type&item);//插入新元素
// BinTreeNode<Type>*Find(Type&item)const;//搜索
void CreateBinTree(ifstream& in,BinTreeNode<Type>*&subTree);//文件读入建树
void printBTree(BinTreeNode<Type>*BT);
protected:
BinTreeNode<Type>*root;//根指针
Type RefValue; //数据停止标志
int Height(BinTreeNode<Type>*subTree);
int Size(BinTreeNode<Type>*subTree)const;
void PreOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p));
void InOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p));
void PostOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p));
// bool Insert(BinTreeNode<Type>*&subTree,const T&x);
void destory(BinTreeNode<Type>*subTree);
// bool Find(BinTreeNode<Type>*subTree,const T&x)const;
// BinTreeNode<Type>*Copy(BinTreeNode<Type>*orignode);
// BinTreeNode<Type>*Parent(BinTreeNode<Type>*subTree,BinTreeNode<T>*current);
// BinTreeNode<Type>*Find(BinTreeNode<Type>*subTree,const T& x)const;
// friend istream& operator>>(istream& in,BinaryTree<T>&Tree);
// friend ostream& operator<<(ostream& out,BinaryTree<T>&Tree);
};
template<class Type>
void BinaryTree<Type>::CreateBinTree(ifstream& in,BinTreeNode<Type>*&subTree)
{
T item;
if(!in.eof()){
in>>item;
if(item!=RefValue){
subTree=new BinTreeNode<Type>(item);
if(subTree==NULL)
{cerr<<"存储分配错误!"<<endl;exit(1);}
CreateBinTree(in,subTree->leftChild);
CreateBinTree(in,subTree->rightChild);
}
else subTree=NULL;
}
}
template<class Type>
void BinaryTree<Type>::printBTree(BinTreeNode<Type>*BT){
if(BT!=NULL){
cout<<BT->data;
if(BT->leftChild!=NULL||BT->rightChild!=NULL)
cout<<'(';
PrintBTree(BT->leftChild);
cout<<',';
if(BT->rightChild!=NULL)
PrintBTree(BT->rightChild);
cout<<')';
}
}
template<class Type>
void BinaryTree<Type>::PostOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p)){
if(subTree!=NULL){
visit(subTree);
cout<<subTree->data<<endl;
PreOrder(subTree->leftChild,visit);
PreOrder(subTree->rightChild,visit);
}
}
template<class Type>
void BinaryTree<Type>::InOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p)){
if(subTree!=NULL){
InOrder(subTree->leftChild,visit);
visit(subTree);
cout<<subTree->data<<endl;
InOrder(subTree->rightChild,visit);
}
}
template<class Type>
void BinaryTree<Type>::PostOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p)){
if(subTree!=NULL){
PostOrder(subTree->leftChild,visit);
PostOrder(subTree->rightChild,visit);
visit(subTree);
cout<<subTree->data<<endl;
}
}
template<class Type>
void BinaryTree<Type>::levelOrder(void(*visit)(BinTreeNode<Type>*p)){
SeqQueue<BinTreeNode<Type>*> Q;
BinTreeNode<Type> *p=root;
Q.EnQueue(p);
while(!Q.IsEmpty()){
Q.DeQueue(p);visit(p);
if(p->leftChild!=NULL)
Q.EnQueue(p->leftChild);
if(p->rightChild!=NULL)
Q.EnQueue(p->rightChild);
}
}
//私有函数计算以*subTree为根二叉树的结点个数
template<class Type>
int BinaryTree<Type>::Size(BinTreeNode<Type> *subTree)const{
if(subTree==NULL)
return 0;
else
return (1+Size(subTree->leftChild)+Size(subTree->rightChild));
}
/*私有函数计算以*subTree 为根的二叉树的深度
template<class Type>
int BinaryTree<Type>::Height(BinTreeNode<Type> *subTree)const{
if(subTree==NULL)return 0;
else{
int i=Height(subTree->leftChild);
int j=Height(subTree->rightChild);
return(i<j)?j+1:i+1;
}
}*/
template<class Type>
void BinaryTree<Type>::destory(BinTreeNode<Type>*subTree){
if(subTree!=NULL){
destory(subTree->leftChild);
destory(subTree->rightChild);
delete subTree;
}
}
#include"SeqQueue.cpp"
template<class Type>
struct BinTreeNode{
Type data;
BinTreeNode<Type> * leftChild, * rightChild;
BinTreeNode():leftChild(NULL),rightChild(NULL){}
BinTreeNode(Type x,BinTreeNode<Type> * l = NULL,BinTreeNode<Type> * r = NULL)
:data(x),leftChild(l),rightChild(r){}
};
template<class Type>
class BinaryTree{
public:
BinaryTree():root(NULL){}
BinaryTree(Type value):ReValue(value),root(NULL){}
~BinaryTree(){destory(root);}
bool IsEmpty(){return(root==NULL)?true:false;}
BinTreeNode<Type>*Parent(BinTreeNode<Type>*current){return(root==NULL||root==current)?NULL:Parent(root,current);}//返回父节点
BinTreeNode<Type>*LeftChild(BinTreeNode<Type>*current){return(current!=NULL)?current->leftChild:NULL;}//返回左子女
BinTreeNode<Type>*RightChild(BinTreeNode<Type>*current){return(current!=NULL)?current->rightChild:NULL;}//返回右子女
int Height(){return Size(root);}
BinTreeNode<Type>*getRoot()const{return root;}
void preOrder(void(*visit)(BinTreeNode<Type>*p)){PreOrder(root,visit);}//前序
void inOrder(void(*visit)(BinTreeNode<Type>*p)){InOrder(root,visit);}//中序遍历
void postOrder(void(*visit)(BinTreeNode<Type>*p)){PostOrder(root,visit);}//后续遍历
void levelOrder(void(*visit)(BinTreeNode<Type>*p));//层序
// int Insert(const Type&item);//插入新元素
// BinTreeNode<Type>*Find(Type&item)const;//搜索
void CreateBinTree(ifstream& in,BinTreeNode<Type>*&subTree);//文件读入建树
void printBTree(BinTreeNode<Type>*BT);
protected:
BinTreeNode<Type>*root;//根指针
Type RefValue; //数据停止标志
int Height(BinTreeNode<Type>*subTree);
int Size(BinTreeNode<Type>*subTree)const;
void PreOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p));
void InOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p));
void PostOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p));
// bool Insert(BinTreeNode<Type>*&subTree,const T&x);
void destory(BinTreeNode<Type>*subTree);
// bool Find(BinTreeNode<Type>*subTree,const T&x)const;
// BinTreeNode<Type>*Copy(BinTreeNode<Type>*orignode);
// BinTreeNode<Type>*Parent(BinTreeNode<Type>*subTree,BinTreeNode<T>*current);
// BinTreeNode<Type>*Find(BinTreeNode<Type>*subTree,const T& x)const;
// friend istream& operator>>(istream& in,BinaryTree<T>&Tree);
// friend ostream& operator<<(ostream& out,BinaryTree<T>&Tree);
};
template<class Type>
void BinaryTree<Type>::CreateBinTree(ifstream& in,BinTreeNode<Type>*&subTree)
{
T item;
if(!in.eof()){
in>>item;
if(item!=RefValue){
subTree=new BinTreeNode<Type>(item);
if(subTree==NULL)
{cerr<<"存储分配错误!"<<endl;exit(1);}
CreateBinTree(in,subTree->leftChild);
CreateBinTree(in,subTree->rightChild);
}
else subTree=NULL;
}
}
template<class Type>
void BinaryTree<Type>::printBTree(BinTreeNode<Type>*BT){
if(BT!=NULL){
cout<<BT->data;
if(BT->leftChild!=NULL||BT->rightChild!=NULL)
cout<<'(';
PrintBTree(BT->leftChild);
cout<<',';
if(BT->rightChild!=NULL)
PrintBTree(BT->rightChild);
cout<<')';
}
}
template<class Type>
void BinaryTree<Type>::PostOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p)){
if(subTree!=NULL){
visit(subTree);
cout<<subTree->data<<endl;
PreOrder(subTree->leftChild,visit);
PreOrder(subTree->rightChild,visit);
}
}
template<class Type>
void BinaryTree<Type>::InOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p)){
if(subTree!=NULL){
InOrder(subTree->leftChild,visit);
visit(subTree);
cout<<subTree->data<<endl;
InOrder(subTree->rightChild,visit);
}
}
template<class Type>
void BinaryTree<Type>::PostOrder(BinTreeNode<Type>*subTree,void(*visit)(BinTreeNode<Type>*p)){
if(subTree!=NULL){
PostOrder(subTree->leftChild,visit);
PostOrder(subTree->rightChild,visit);
visit(subTree);
cout<<subTree->data<<endl;
}
}
template<class Type>
void BinaryTree<Type>::levelOrder(void(*visit)(BinTreeNode<Type>*p)){
SeqQueue<BinTreeNode<Type>*> Q;
BinTreeNode<Type> *p=root;
Q.EnQueue(p);
while(!Q.IsEmpty()){
Q.DeQueue(p);visit(p);
if(p->leftChild!=NULL)
Q.EnQueue(p->leftChild);
if(p->rightChild!=NULL)
Q.EnQueue(p->rightChild);
}
}
//私有函数计算以*subTree为根二叉树的结点个数
template<class Type>
int BinaryTree<Type>::Size(BinTreeNode<Type> *subTree)const{
if(subTree==NULL)
return 0;
else
return (1+Size(subTree->leftChild)+Size(subTree->rightChild));
}
/*私有函数计算以*subTree 为根的二叉树的深度
template<class Type>
int BinaryTree<Type>::Height(BinTreeNode<Type> *subTree)const{
if(subTree==NULL)return 0;
else{
int i=Height(subTree->leftChild);
int j=Height(subTree->rightChild);
return(i<j)?j+1:i+1;
}
}*/
template<class Type>
void BinaryTree<Type>::destory(BinTreeNode<Type>*subTree){
if(subTree!=NULL){
destory(subTree->leftChild);
destory(subTree->rightChild);
delete subTree;
}
}

Compiling...
BinaryTree.cpp
d:\c++\5\二叉树\binarytree.cpp(30) : error C2061: syntax error : identifier 'ifstream'
d:\c++\5\二叉树\binarytree.cpp(49) : see reference to class template instantiation 'BinaryTree<Type>' being compiled
d:\c++\5\二叉树\binarytree.cpp(51) : error C2061: syntax error : identifier 'ifstream'
d:\c++\5\二叉树\binarytree.cpp(105) : error C2995: 'PostOrder' : template function has already been defined
d:\c++\5\二叉树\binarytree.cpp(39) : see declaration of 'PostOrder'
执行 cl.exe 时出错.