binarytree.h

包括图、二叉树、链表

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include"BinaryNode.h"
#include <queue>
template<class Entry>
class BinaryTree
{
public:
	BinaryTree();
	bool empty();
	void preorder(void(*visit)(Entry&));
	void inorder(void(*visit)(Entry&));
	void postorder(void(*visit)(Entry&));
	int height() const;
	void insert(const Entry& x);
	void build_tree(queue<Entry>& x);
	
private:
	void recursive_inorder(BinaryNode<Entry>*sub_root,void(*visit)(Entry&));
	void recursive_preorder(BinaryNode<Entry>*sub_root,void(*visit)(Entry&));
	void recursive_postorder(BinaryNode<Entry>*sub_root,void(*visit)(Entry&));
    int  recursive_height(BinaryNode<Entry> *sub_root) const;
	void recursive_insert(BinaryNode<Entry> * &sub_root,const Entry &x);
	BinaryNode<Entry>* root;
	queue<BinaryNode<Entry>*> q;
};

template<class Entry>
BinaryTree<Entry>::BinaryTree()
{
	root=NULL;
}
template<class Entry>
bool BinaryTree<Entry>::empty()
{
	return root==NULL;
}
template<class Entry>
void BinaryTree<Entry>::preorder(void(*visit)(Entry&))
{
	recursive_preorder(root,visit);
}
template<class Entry>
void BinaryTree<Entry>::inorder(void(*visit)(Entry&))
{
	recursive_inorder(root,visit);
}
template<class Entry>
void BinaryTree<Entry>::postorder(void(*visit)(Entry&))
{
	recursive_postorder(root,visit);

}
template<class Entry>
void BinaryTree<Entry>::recursive_inorder(BinaryNode<Entry>*sub_root,void(*visit)(Entry&))
{
	if(sub_root!=NULL)
	{
		recursive_inorder(sub_root->left,visit);
		(*visit)(sub_root->data);
		recursive_inorder(sub_root->right,visit);
	}
}
template<class Entry>
void BinaryTree<Entry>::recursive_preorder(BinaryNode<Entry>*sub_root,void(*visit)(Entry&))
{
	if(sub_root!=NULL)
	{
		(*visit)(sub_root->data);
		recursive_preorder(sub_root->left,visit);
		recursive_preorder(sub_root->right,visit);
	}
}
template<class Entry>
void BinaryTree<Entry>::recursive_postorder(BinaryNode<Entry>*sub_root,void(*visit)(Entry&))
{
	if(sub_root!=NULL)
	{
		recursive_postorder(sub_root->left,visit);
		recursive_postorder(sub_root->right,visit);
		(*visit)(sub_root->data);
	}
}

template <class Entry>
int BinaryTree<Entry> :: height( ) const
{
   return recursive_height(root);
}
template <class Entry>
int BinaryTree<Entry> :: recursive_height(BinaryNode<Entry> *sub_root) const
{
     if (sub_root == NULL) return 0;
     int l = recursive_height(sub_root->left);
     int r = recursive_height(sub_root->right);
     if (l > r) return (l+1);
     else return (r+1);
}
template <class Entry>
void BinaryTree<Entry> :: insert(const Entry &x)
{
	 recursive_insert(root, x);   
}
template <class Entry>
void BinaryTree<Entry> :: recursive_insert(BinaryNode<Entry> * &sub_root,const Entry &x)
{
   if (sub_root == NULL)  sub_root = new BinaryNode<Entry>(x);
   else if(recursive_height(sub_root->right) < recursive_height(sub_root->left)) recursive_insert(sub_root->right, x);
	else recursive_insert(sub_root->left, x);
   
}
template<class Entry>
void BinaryTree<Entry>::build_tree(queue<Entry>& x)
{
	BinaryNode<Entry>* temp,*t;
	Entry c1,c2;
	while(!x.empty())
	{
		if(root==NULL)
		{
		  c1=x.front();
		  x.pop();
		  if(c1!=(Entry)('.'))
		  {
			root=new BinaryNode<Entry>(c1);
		    q.push(root);
		    
		  }
		else
		{
			root=NULL;
			c1=x.front();
		}
	 }
	   
	else
	{ 
		if(!x.empty())
		{
			temp=q.front();
           c1=x.front();
		   x.pop();
		   if(c1!=(Entry)('.'))
		   {
               t=new BinaryNode<Entry>(c1);
			   temp->left=t;
			   q.push(t);
		   }
		   if(!x.empty())
		   {
			   c2=x.front();
			   x.pop();
			   if(c2!=(Entry)('.'))
			   {
                  t=new BinaryNode<Entry>(c2);
			      temp->right=t;
			      q.push(t);
			   }
		   }
		   q.pop();
		}
	}
	}
}
#endif