07.cpp

来自「用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）」· C++ 代码 · 共 133 行

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

template<class T>
class BinaryTreeNode
{
	public:
		BinaryTreeNode() { LeftChild=RightChild=0;}
		BinaryTreeNode(const T& e)
		{ data=e;LeftChild=RightChild=0;}
		BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r)
		{ data=e;LeftChild=l;RightChild=r;}
	private:
		T data;
		BinaryTreeNode<T> *LeftChild,
			              *RightChild;
}
template<class T>
class BinaryTree
{
	public:
		BinaryTree() {root=0;};
		~BinaryTree() {};
		bool Empty() 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 PreOutput() {PreOrder(Output,root);out<<endl;}
		void InOutput() {InOrder(Output,root);out<<endl;}
		void PostOutput() {PostOrder(Output,root);out<<endl;}
		void Delete() {PostOrder(Free,root);root=0;}
		int Height() const {return Height(root);}
		int Size() {count=0;PreOrder(Addl,root);return count;}
	private:
		BinaryTreeNode<T> *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) {out<<t->data<<' ';}
		static void Addl(BinaryTreeNode<T> *t) {count++;}
		int Height(BinaryTreeNode<T> *t) const;
}
template<class T>
bool BinaryTree<T>::Root(T&x)const
{
	if(root) {x=root->data; return true;}
	else return false;
}
template<class T>
void BinaryTree<T>::MakeTree(const T& element,BinaryTree<T>&left,BinaryTree<T>&right)
{
	root=new BinaryTreeNode<T>(element,left.root,right.root);
	left.root=right.root=0;
}
template<class T>
void BinaryTree<T>::BreakTree(T& element,BinaryTree<T>&left,BinaryTree<T>&right)
{
//	if(!root) throw BadInput();
	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)
{
	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)
{
	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)
{
	if(t)
	{		
		PostOrder(Visit,t->LeftChild);
		PostOrder(Visit,t->RightChild);
		Visit(t);
	}
}
template<class T>
int BinaryTree<T>::Height(BinaryTreeNode<T> *t) const
{ 
	if(!t)return 0;
	int hl=Height(t->LeftChild);
	int hr=Height(t->RightChild);
	if(hl>hr)return ++hl;
	else return ++hr;
}
////////////////////////////////////////////////////////////////////////
template<class T>
class ThreadedNode
{
	friend ThreadedTree<T>;
	public:
        ThreadedNode() {LeftChild=RightChild=0;}
	private:
		T data;
		ThreadedNode<T> *LeftChild,
			            *RightChild;
		bool LeftThread,RightThread
}