binarytree.h

提供文本的无损压缩功能

#ifndef BINARYTREE_
#define BINARYTREE_
#include "BinaryTreeNode.h"
#include "Stack.h"
class   huffman;
template<class T>
class BinaryTree
{
	 friend huffman;
public:
	BinaryTree() {root = 0;};

	 ~BinaryTree(){}; 
    void MakeTree(const T& element,BinaryTree<T>& left,BinaryTree<T>& right);
   
    void BreakTree(  BinaryTree<T>& left, BinaryTree<T>& right);

	int Height() const {return Height(root);}
	void OuthuffmanTreePath(  char **c  ,int n)
	{
		char* ch=new char[n]; 

       outhuffmantreepath(c,root,ch,0);
	   delete []ch;
	}
	bool huffmanTreeLeaves()
	{
		return root->LeftChild?true:false;
		 
	}
	T &Data(){return root->data;}
   //void Getcode(char **a,int num){char* ch=new char[num]; Getcode(a,root,ch,0);delete []ch;};////获得编码


private:
	void outhuffmantreepath( char *ch[],BinaryTreeNode<T>* t,char *,int n);
//	void Getcode(char *[],BinaryTreeNode<T> *t,char *,int); /////获得编码

	BinaryTreeNode<T> *root;
	int Height(BinaryTreeNode<T> *t) const;
  
};
template<class T>
void  BinaryTree<T>::outhuffmantreepath(char **ch , BinaryTreeNode<T> *t,char*path, int i)
{
	 
	if(t)
	{
		if(!t->LeftChild&&!t->RightChild)
		{
			path[i]='\0';
			strcpy(ch[t->data],path);
		}
      path[i]='0';
	  outhuffmantreepath(ch,t->LeftChild,path,i+1);
	  path[i]='1';
	  outhuffmantreepath(ch,t->RightChild,path,i+1);
	}
}
 
template<class T>
void BinaryTree<T>::MakeTree(const T& element,BinaryTree<T>& left, BinaryTree<T>& right)
{// Combine left, right, and element to make new tree.
	// left, right, and this must be different trees.
	// create combined tree
	root = new BinaryTreeNode<T>(element, left.root, right.root);
	
	// deny access from trees left and right
	left.root = right.root = 0;
}
template<class T>
void BinaryTree<T>::BreakTree(  BinaryTree<T>& left, BinaryTree<T>& right)
{// left, right, and this must be different trees.
   // check if empty
   if (!root) 
	   throw BadInput(); // tree empty

   // break the tree
   
   left.root = root->LeftChild;
   right.root = root->RightChild;
}
template <class T>
int BinaryTree<T>::Height(BinaryTreeNode<T> *t) const
{// Return height of tree *t.
   if (!t) 
	   return 0;               // empty tree
   int hl = Height(t->LeftChild);  // height of left
   int hr = Height(t->RightChild); // height of right
   if (hl > hr) 
	   return ++hl;
   else return ++hr;
}
//template <class T>
//void BinaryTree<T>::OuthuffmanTreePath(int freqency[], char *ch[], int n)
//{
//
//}
#endif