linkquee.h

一个最简单的二叉树的算法

template<class T> class BinaryTree;
template<class T>
class LinkedQueue {
	friend class BinaryTree<T>;
public:
	LinkedQueue() {front = rear = 0;} 
	~LinkedQueue(); 
	bool IsEmpty() const
	{
		return ((front) ? false : true);
	}
	bool IsFull() const;
	T First() const; 
	T Last() const;
	LinkedQueue<T>& Add(const T& x);
	LinkedQueue<T>& Delete(T &x);
private:
	BinaryTreeNode<T> *front; 
	BinaryTreeNode<T> *rear;
};
template<class T>
LinkedQueue<T>::~LinkedQueue()
{
	BinaryTreeNode<T> *next;
	while (front) {
		next = front->Right;
	delete front;
	front = next;
	}
}
template<class T>
bool LinkedQueue<T>::IsFull() const
{
	BinaryTreeNode<T> *p;
	try 
	{p = new BinaryTreeNode<T>;
	delete p;
	return false;}
	catch (NoMem) {return true;}
}
template<class T>
T LinkedQueue<T>::First() const
{
	if (IsEmpty()) 
		throw OutOfBounds();
	return front->data;
}
template<class T>
T LinkedQueue<T>::Last() const
{
	if (IsEmpty()) throw OutOfBounds();
	return rear->data;
}
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
{
	BinaryTreeNode<T> *p = new BinaryTreeNode<T>;
	p->data = x;
	p->link = 0;
	if (front) 
		rear->link = p; 
	else 
		front = p; 
	rear = p;
	return *this;
}
template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{
	if (IsEmpty()) throw OutOfBounds();
	x = front->data;
	BinaryTreeNode<T> *p = front;
	front = front->Right;
	delete p;
	return *this;
}