binary.h

常用算法与数据结构原代码

// file binary.h

#ifndef BinaryTree_
#define BinaryTree_
int _count;

#include <iostream.h>
#include "lqueue.h"
#include "btnode.h"
#include "xcept.h"
#include "swap.h"

template<class E, class K> class DBSTree;

template<class T>
class BinaryTree 
{
	friend DBSTree<T,int>;
public:
	BinaryTree() 
	{
		root = 0;
	};
	BinaryTree(const BinaryTree<T>& B)
	{
		root=PostCopy(B.root);
	}
	~BinaryTree()
	{
		Delete();
	}; 
	bool IsEmpty() const
	{
		return ((root) ? false : true);
	}
	bool Root(T& x) const;
	void MakeTree(const T& element,	BinaryTree<T>& left, BinaryTree<T>& right);
	void BreakTree(T& element, BinaryTree<T>& left, BinaryTree<T>& right);
	void PreOrder(void(*Visit)(BinaryTreeNode<T> *u))
	{
		PreOrder(Visit, root);
	}
	void InOrder(void(*Visit)(BinaryTreeNode<T> *u))
	{
		InOrder(Visit, root);
	}
	void PostOrder(void(*Visit)(BinaryTreeNode<T> *u))
	{
		PostOrder(Visit, root);
	}
	void LevelOrder(void(*Visit)(BinaryTreeNode<T> *u));
	void PreOutput() 
	{
		PreOrder(Output, root); 
		cout << endl;
	}
	void InOutput() 
	{
		InOrder(Output, root); 
		cout << endl;
	}
	void PostOutput() 
	{
		PostOrder(Output, root); 
		cout << endl;
	}
	void LevelOutput() 
	{
		LevelOrder(Output); 
		cout << endl;
	}
	void Delete()
	{
		PostOrder(Free, root); 
		root = 0;
	}
	int Height() const 
	{
		return Height(root);
	}
	int Size()
	{
		_count = 0; 
		PreOrder(Add1, root); 
		return _count;
	}
	bool Compare(const BinaryTree<T>& t)
	{
		return Compare(root, t.root);
	}
	BinaryTree<T>& SwapChildren()
	{
		SwapChildren(root); 
		return *this;
	}  
	BinaryTree<T>& operator =(const BinaryTree<T>& B)
	{
		root = PostCopy(B.root);
		return *this;
	}
	BinaryTree<T>& PostCopy(BinaryTree<T>& B)
	{ 
		if(this==&B) 
			return *this;
		Delete();
		root=PostCopy(B.root); 
		return *this;
	}
	BinaryTree<T>& PreCopy(BinaryTree<T>& B)
	{ 
		if(this==&B) 
			return *this; 
		Delete();
		root=PreCopy(B.root); 
		return *this;
	}
private:
	BinaryTreeNode<T> *root;  // pointer to root
	void PreOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
	void InOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
	void PostOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t);
	static void Free(BinaryTreeNode<T> *t) 
	{
		delete t;
	}
	static void Output(BinaryTreeNode<T> *t)
	{
		cout << t->data << ' ';
	}
	static void Add1(BinaryTreeNode<T> *t) 
	{
		_count++;
	}
	int Height(BinaryTreeNode<T> *t) const;
	bool Compare(BinaryTreeNode<T> *t,BinaryTreeNode<T> *u);
	void SwapChildren(BinaryTreeNode<T> * &t);
	BinaryTreeNode<T>* PostCopy(BinaryTreeNode<T> *t);
	BinaryTreeNode<T>* PreCopy(BinaryTreeNode<T> *t);
};

template<class T>
bool BinaryTree<T>::Root(T& x) const
{// Return root data in x.
	// Return false if no root.
	if (root) 
	{
		x = root->data;
		return true;
	}
	else 
		return false;  // no root
}

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
	if (&left == &right && left.root != 0) 
		return;
	if (this == &left || this == &right)
		return;

	Delete();
	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(T& element, BinaryTree<T>& left, BinaryTree<T>& right)
{// left, right, and this must be different trees.
	// check if empty
	if (this == &left || this == &right || &left == &right) 
		return;
	if (!root) 
		throw BadInput(); // tree empty
	// break the tree
	element = root->data;
	left.root = root->LeftChild;
	right.root = root->RightChild;
	
	delete root;
	root = 0;
}

template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
{// Preorder traversal.
	if (t) 
	{
		Visit(t);
		PreOrder(Visit, t->LeftChild);
		PreOrder(Visit, t->RightChild);
	}
}

template <class T>
void BinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
{// Inorder traversal.
	if (t)
	{
		InOrder(Visit, t->LeftChild);
		Visit(t);
		InOrder(Visit, t->RightChild);
	}
}

template <class T>
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
{// Postorder traversal.
	if (t) 
	{	PostOrder(Visit, t->LeftChild);
		PostOrder(Visit, t->RightChild);
		Visit(t);
	}
}

template <class T>
void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode<T> *u))
{// Level-order traversal.
	LinkedQueue<BinaryTreeNode<T>*> Q;
	BinaryTreeNode<T> *t;
	t = root;
	while (t) 
	{
		Visit(t);
		if (t->LeftChild) 
			Q.Add(t->LeftChild);
		if (t->RightChild) 
			Q.Add(t->RightChild);
		try
		{
			Q.Delete(t);
		}
		catch (OutOfBounds) 
		{
			return;
		}
	}
}

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>
bool BinaryTree<T>::Compare(BinaryTreeNode<T> *t, BinaryTreeNode<T> *u)
{// Use a preorder traversal to compare the
	// two binary (sub)trees t and u.
	// Return true iff t and u are identical.
	if (!t && !u) 
		return true;  // both empty
	if (!t || !u) 
		return false; // only one is empty
	// neither is empty
	if (t->data != u->data) 
		return false; // different data
	return  Compare(t->LeftChild, u->LeftChild) && Compare(t->RightChild, u->RightChild);
}

template<class T>
void BinaryTree<T>::SwapChildren(BinaryTreeNode<T> * &t)
{// Swap the children of every node in the subtree t.
	// Do a postorder traversal; swap left and right child
	// pointers in the visit step.
	if (t) 
	{// t is not null
		SwapChildren(t->LeftChild);
		SwapChildren(t->RightChild);
		Swap(t->LeftChild, t->RightChild);
	}
}

template <class T>
BinaryTreeNode<T>* BinaryTree<T>::PostCopy(BinaryTreeNode<T> *t)
{// Copy the subtree t using a postorder traversal.
	// Return a pointer to the root of the new tree.
	if (!t) // t is empty
		return 0;
	// first make copies of left and right subtrees
	BinaryTreeNode<T> *left, *right, *root;
    left = PostCopy(t->LeftChild);
	try
	{
		right = PostCopy(t->RightChild);
	}
	catch (...) 
	{
		// copy failed, free nodes in left subtree
		Free(left);
		throw;
	}  // rethrow exception
	// successful copy of left and right subtrees
	// copy root
	try 
	{
		root = new BinaryTreeNode<T>(t->data, left, right);
	}
	catch (...) 
	{
		// failed to get a node for root
		// free nodes in left and right subtrees
		Free(left);
		Free(right);
		throw;
	}
	return root;
}

template <class T>
BinaryTreeNode<T>* BinaryTree<T>::PreCopy(BinaryTreeNode<T> *t)
{// Copy the subtree t using a postorder traversal.
	// Return a pointer to the root of the new tree.
	if (!t) // t is empty
		return 0;
	// first make a copy of the root
	BinaryTreeNode<T> *root;
	root = new BinaryTreeNode<T> (t->data);
	// now make a copy of the left subtree
	try 
	{
		root->LeftChild = PreCopy(t->LeftChild);
	}
	catch (...) 
	{
		// copy failed, free root node
		delete root;
		throw;
	}  // rethrow exception
	// now make a copy of the right subtree
	try 
	{
		root->RightChild = PreCopy(t->RightChild);
	}
	catch (...) 
	{
		// copy failed, free nodes in left subtree
		// and the root
		Free(root->LeftChild);
		delete root;
		throw;
	}  // rethrow exception
	return root;
}

#endif