2叉树类定义.txt

一些很好用的数据结构

//二叉树类定义
template<class T>
class BinaryTree {
public :
BinaryTree( ) {root=0;};
~ BinaryTree( ) { };
bool IsEmpty( ) const
{reurn ((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(Visitroot) ; }
void PostOrder(void(*Visit ) (BinaryTreeNode<T> *u));
{Postorder Visit, root); }
void LevelOrder(void(*Visit) (BinaryTreeNode<T> *u));
private :

BinaryTree<T> *root; // 根节点指针 

void PreOrder(void(*Visit) (BinaryTreeNode<T> *u)，BinaryTree<T> *t);
void InOrder(void(*Visit) (BinaryTreeNode<T> *u)，BinaryTree<T> *t);
void PostOrder(void(*Visit) (BinaryTreeNode<T> *u)，BinaryTree<T> *t);
} ;
 





template<class T>
bool BinaryTree<T>::Root(T& x) const
{
// 取根节点的data域放入x
// 如果没有根节点，则返回false
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)
{
// 将left, right和element 合并成一棵新树
// left,right和this必须是不同的树
// 创建新树
root = new BinaryTreeNode< T >(element, left.root, right.root);
// 阻止访问left和right
left.root = right.root=0;
}
template<class T>
void BinaryTree <T>:: BreakTree(T& element, BinaryTree<T>& left, BinaryTree<T>& right)
{
// left, right和t h i s必须是不同的树
// 检查树是否为空
if (!root) cout<<"It's empty"; // 空树
// 分解树
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>
void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode<T> *u))
{
// 逐层遍历
LQueue <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);
Q.Delete(t)
}
}