binarytree.h.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > asd.rar > BinaryTree.h


#ifndef BINARYTREE 
#define BINARYTREE 

#include<iostream.h> 
#include "Queue.h" 


template<class Type> class BinaryTree; 
template<class Type> class FullBinaryTree; 
template<class Type> class BinTreeNode 
{ 
friend class BinaryTree<Type>; 
friend class FullBinaryTree<Type>; 

public: 
BinTreeNode():leftChild(NULL),rightChild(NULL){} 
BinTreeNode(Type item,BinTreeNode<Type> *left=NULL, 
BinTreeNode<Type> * right=NULL):data(item), 
leftChild(left),rightChild(right){} 
Type GetData() const{return data;} 
BinTreeNode<Type> *GetLeft() const{ return leftChild;} 
BinTreeNode<Type> *GetRight() const{ return rightChild;} 
void SetData(const Type &amt; item){ data=item;} 
void SetLeft(BinTreeNode<Type> *L){ leftChild=L;} 
void SetRight(BinTreeNode<Type> * R){ rightChild=R;} 
private: 
BinTreeNode<Type> *leftChild,* rightChild; 
Type data; 
}; 


template<class Type> class BinaryTree 
{ 
public: 
BinaryTree():root(NULL){} 
BinaryTree(Type value) 
:RefValue(value),root(NULL) {} 

virtual int IsEmpty(){ return root==NULL?1:0;} 
virtual BinTreeNode<Type> * Parent(BinTreeNode<Type> *current) 
{ 
return root==NULL || root==current? NULL: Parent(root,current); 
} 
virtual BinTreeNode<Type> *LeftChild(BinTreeNode<Type> *current) 
{ 
return root!=NULL ? current->leftChild:NULL; 
} 
virtual BinTreeNode<Type> * RightChild(BinTreeNode<Type> * current) 
{ 
return root!=NULL ? current->rightChild:NULL; 
} 
virtual int Insert(const Type &amt; item)=0; 
virtual int Find(const Type &amt; item)const; 
virtual void print(ostream &amt;out){}; 
virtual void destory(){destory(root);} 
const BinTreeNode<Type> * GetRoot() const { return root;} 
friend istream &amt;operator >> (istream &amt; in,BinaryTree<Type> &amt; Tree); 
friend ostream &amt; operator<< (ostream &amt; out,BinaryTree<Type> &amt; Tree); 
protected: 
BinTreeNode<Type> * root; 
BinTreeNode<Type> * current; 
Type RefValue; 

int depth(BinTreeNode<Type> *current); 
//以current为根结点的二插树的高度 
int depth(){ return depth(root)-1;} 
//二叉树高度 若为空树则返回-1 

virtual int Insert(BinTreeNode<Type>* current,const Type &amt; item)=0; 
private: 
BinTreeNode<Type> * Parent(BinTreeNode<Type> * start,BinTreeNode<Type> * current); 
void destory(BinTreeNode<Type> * current); 
void Traverse(BinTreeNode<Type> *current,ostream &amt; out) const; 
int Find(BinTreeNode<Type> * current,const Type &amt; item) const; 

}; 

template<class Type> void BinaryTree<Type>::destory(BinTreeNode<Type> * current) 
{ 
if(current!=NULL) 
{ 
destory(current->leftChild); 
destory(current->rightChild); 
delete current; 
} 
} 


template<class Type> BinTreeNode<Type> * BinaryTree<Type>::Parent(BinTreeNode<Type> * start, 
BinTreeNode<Type>* current) 
{ 
if(start==NULL) return NULL; 
if(start->leftChild==current|| start->rightChild==current) return start; 
BinTreeNode<Type> * p; 
if((p=Parent(start->leftChild,current))!=NULL) return p; 
else return Parent(start->rightChild,current); 
} 

template<class Type> void BinaryTree<Type>::Traverse(BinTreeNode<Type> * current,ostream &amt; out) const 
{ 
if(current!=NULL) 
{ 
out<<current->data<<' '; 
Traverse(current->leftChild,out); 
Traverse(current->rightChild,out); 
} 
} 

template<class Type> istream &amt; operator>> (istream &amt; in,BinaryTree<Type>&amt; Tree) 
{ 
Type item; 
cout<<endl; 
cout<<"Construct binary tree:\n"; 
cout<<"Input data(end with:"<<Tree.RefValue<<"):"; 
in>>item; 
while(item!=Tree.RefValue) 
{ 
Tree.Insert(item); 
// cout<<"Input data(end with"<<Tree.RefValue<<"):"; 
in>>item; 
} 
return in; 
} 

template<class Type> ostream &amt; operator<<(ostream &amt; out,BinaryTree<Type>&amt; Tree) 
{ 
out<<"Preorder Traversal of binary tree:\n"; 
Tree.Traverse(Tree.root,out); 
out<<endl; 
return out; 
} 

template<class Type> int BinaryTree<Type>::Find(BinTreeNode<Type> * current,const Type &amt; item) const 
{ 
if(current==NULL) return 0; 
else 
{ 
if(current->data==item) return 1; 
else if(Find(current=current->leftChild,item)==1) return 1; 
else if(Find(current=current->rightChild,item)==1) return 1; 
else 
return 0; 
} 
} 




template<class Type> int BinaryTree<Type>::Find(const Type &amt; item) const 
{ 
if(Find(current,item)) return 1; 
return 0; 
} 
template<class Type> int BinaryTree<Type>::depth(BinTreeNode<Type> *current) 
{ 
if(current==NULL) return 0; 
else 
{ 
int d1,d2; 
d1=depth(current->leftChild)+1; 
d2=depth(current->rightChild)+1; 
if(d1>d2) return d1; 
else 
return d2; 
} 
} 
#endif