www.pudn.com > compressor.zip > BinaryTree.h
#ifndef BinaryTree_H
#define BinaryTree_H
#include
#include
#include
#include
#include"BinTreeNode.h"
#include"MinHeap.h"
#include
template
class BinaryTree
{
private:
BinTreeNode *root;
BinTreeNode *Parent(BinTreeNode *start,BinTreeNode *current);
void Insert(BinTreeNode* &Ptr,const T& item);
T MaxValue(BinTreeNode* Ptr,T& Max);
BinTreeNode* GetNode(const T item,BinTreeNode* &Ptr);
void print(BinTreeNode *current,ostream& out) const;
int Find(BinTreeNode *current,const T& item) const;
int level(BinTreeNode *t,BinTreeNode *p);
BinTreeNode* Copy(BinTreeNode *node);
public:
void destroy(BinTreeNode *current);
BinaryTree():root(NULL){}
BinaryTree(BinaryTree &T) {root = Copy(T.root);}
~BinaryTree() {destroy(root);}
int IsEmpty(){return root==NULL?1:0;}
BinTreeNode* GetNode(const T item);
BinTreeNode* Parent(BinTreeNode *current)
{return root==NULL||root==current ? NULL : Parent(root,current);}
BinTreeNode* Parent(const T& item);
int level(const T& item,int &lev);
BinaryTree& MakeTree(const BinaryTree& lt,const BinaryTree& rt);
void HuffmanTree(T item[],int frqu[],int n,BinaryTree& newTree);
void Decoding(int code[],int n);
void Coding(T& item,int a[]);
void Coding(char *filename1,char *filename2,BinaryTree& Tree);
void Decoding(char *file,char * codefile,BinaryTree& Tree);
void Insert(const T& item);
void PrintTree(BinTreeNode* Ptr,int level);
void Blanks(int n);
BinTreeNode *GetRoot() {return root;}
bool operator > (const BinaryTree& p)
{
return root->Flag > p.root->Flag;
}
bool operator <= (const BinaryTree& p)
{
return root->Flag <= p.root->Flag;
}
BinaryTree& operator = (const BinaryTree& p);
friend istream& operator >> (istream& is, BinaryTree &Tree);
friend ostream& operator << (ostream& os, const BinaryTree& Tree);
};
template
void BinaryTree::destroy(BinTreeNode *current)
{
if(current != NULL){
destroy(current->leftChild);
destroy(current->rightChild);
delete current;
}
}
template
BinaryTree& BinaryTree::MakeTree(const BinaryTree& lt,const BinaryTree& rt)
{
root = new BinTreeNode;
root->data ='#';
root->Flag = lt.root->Flag + rt.root->Flag;
root->leftChild = lt.root;
root->rightChild = rt.root;
return *this;
}
template
void BinaryTree::HuffmanTree(T item[],int frqu[],int n,BinaryTree& newTree)
{
BinaryTree first,second;
BinaryTree* Node;
Node = new BinaryTree[n];
for(int i=0;i(item[i],frqu[i],NULL,NULL);
}
MinHeap< BinaryTree > heap(Node,n);
for(i=0;i
BinaryTree& BinaryTree::operator = (const BinaryTree& p)
{
root = Copy(p.root);
return *this;
}
template
BinTreeNode* BinaryTree::Copy(BinTreeNode *node)
{
if(node == NULL) return NULL;
BinTreeNode *temp = new BinTreeNode;
temp->data = node->data;
temp->Flag = node->Flag;
temp->leftChild = Copy(node->leftChild);
temp->rightChild = Copy(node->rightChild);
return temp;
}
template
BinTreeNode* BinaryTree::GetNode(const T item)
{
BinTreeNode *p = GetNode(item,root);
return p;
}
template
BinTreeNode* BinaryTree::GetNode(const T item,BinTreeNode* &Ptr)
{
if(Ptr == NULL) return NULL;
else if(Ptr->data == item) return Ptr;
else{
BinTreeNode *p=NULL;
p=GetNode(item,Ptr->leftChild);
if(p!=NULL)
return p;
else
return GetNode(item,Ptr->rightChild);
}
}
template
int BinaryTree::level(const T& item,int& lev)
{
BinTreeNode *p = GetNode(item,root);
int m = level(root,p);
lev = m;
return m;
}
template
int BinaryTree::level(BinTreeNode *t,BinTreeNode *p)
{
int leftLevel=0,rightLevel=0;
if(t==NULL){
return -1;}
if(t==p) return 0;
if((leftLevel = level(t->leftChild,p)) > -1)
return leftLevel + 1;
if((rightLevel = level(t->rightChild,p)) > -1)
return rightLevel + 1;
return -1;
}
template
BinTreeNode* BinaryTree::Parent(const T& item)
{
BinTreeNode* p = GetNode(item);
// cout<
BinTreeNode* BinaryTree::Parent(BinTreeNode *start,BinTreeNode *current)
{
if(start == NULL) return NULL;
if(start->leftChild == current || start->rightChild == current) return start;
BinTreeNode *p;
if((p = Parent(start->leftChild,current)) != NULL) return p;
else return Parent(start->rightChild,current);
}
template
void BinaryTree::Insert(const T& item)
{
Insert(root,item);
}
template
void BinaryTree::Insert(BinTreeNode* &Ptr,const T& item)
{
if(Ptr==NULL){
Ptr = new BinTreeNode(item);
assert(Ptr!=NULL);
// cout<data < item)
Insert(Ptr->rightChild,item);
else if(Ptr->data >= item)
Insert(Ptr->leftChild,item);
}
}
template
void BinaryTree::PrintTree(BinTreeNode* Ptr,int level)
{
if(Ptr!=NULL){
PrintTree(Ptr->rightChild,level+1);
Blanks(3*level);
cout<data<leftChild,level+1);
}
}
template
void BinaryTree::Blanks(int n)
{
for(int i=0;i
void BinaryTree::print(BinTreeNode *current,ostream& os) const
{
if(current != NULL){
os<data<leftChild<rightChild<leftChild, os);
print(current->rightChild, os);
}
}
template
void BinaryTree::Coding(char *filename1,char *filename2,BinaryTree& Tree)
{
*this = Tree;
ifstream fin;
fin.open(filename1);
if(!fin)
{
cout<<"file can't open!"<>item )
while(fin.get(item)){
// cout<";
Coding(item,a);
this->level(item,level);
for(int i=0;i
void BinaryTree::Decoding(int code[],int n)
{
int i=0;
BinTreeNode* p=root;
for(i=0;ileftChild==NULL){
cout<<"NO"<<" ";
p = root; continue;
}
p = p->leftChild;
}
else {
if(p->rightChild==NULL){
cout<<"NO"<<" ";
p = root;continue;
}
p = p->rightChild;
}
if( p->IsLeaf()) {
cout<data<<" ";
p = root;
}
}
cout<
void BinaryTree::Decoding(char *file,char *codefile,BinaryTree& Tree)
{
*this = Tree;
ifstream fin;
fin.open(file);
if(!fin)
{
cout<<"file can't open!"< *p=root;
// while(fin>>temp)
while(fin.get(temp))
{
if(temp=='0'){
if(p->leftChild==NULL){
cout<<"NO"<<" ";fout<<"NO"<<" ";
p = root; continue;
}
p = p->leftChild;
}
else {
if(p->rightChild==NULL){
cout<<"NO"<<" ";fout<<"NO"<<" ";
p = root;continue;
}
p = p->rightChild;
}
if( p->IsLeaf()) {
cout<data;
fout<data;
p = root;
}
}cout<
void BinaryTree::Coding(T& item,int a[])
{
int i=0;int m=0;
level(item,m);
BinTreeNode* p = GetNode(item);
while(p!=root){
BinTreeNode* q = Parent(p);
if(q->leftChild == p) a[--m]=0;
else a[--m]=1;
p = q;
}
}
/*
template
istream& operator >> (istream& is, BinaryTree &Tree)
{
T item;
cout<<"Construct binary tree:"<>item;
while(item != Tree.RefValue){
cout<<"Input data ( end with" << Tree.RefValue <<"):";
is >> item;
}
return is;
}
*/
template
ostream& operator << (ostream& os, const BinaryTree& Tree)
{
Tree.print(Tree.root,os);
return os;
}
#endif