Posted on 2010-04-21 21:01
陈显锋 阅读(248)
评论(0) 编辑 收藏 引用 所属分类:
数据结构程序
#ifndef BINARY_TREE
#define BINARY_TREE
#include<stack>
#include<iostream>
using namespace std;
template<class T> class BinaryTree;
template<class T>
class BTNode
{
public:
BTNode(){lChild=rChild=NULL;}
BTNode(const T&x)
{
element=x;
lChild=rChild=NULL;
}
BTNode(const T& x,BTNode<T>*l,BTNode<T>* r)
{
element=x;lChild=l;rChild=r;
}
friend class BinaryTree<T>;
private:
T element;
BTNode<T>* lChild,*rChild;
static stack<BTNode<T>*> s;
};
template<class T>
stack<BTNode<T>*> BTNode<T>::s;
template<class T>
class BinaryTree
{
public:
BinaryTree(){root=NULL;}
bool IsEmpty()const{return root==NULL}
void Clear();
bool Root(T& x)const;
void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);
void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);
void PreOrder();
protected:
BTNode<T>* root;
private:
void PreOrder(BTNode<T>*current);
};
#endif//BINARY_TREE
template<class T>
bool BinaryTree<T>::Root(T &x)const
{
if(root){
x=root->element;return true;
}
else return false;
}
template<class T>
void BinaryTree<T>::MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)
{
if(root||&left==&right) return;
root=new BTNode<T>(x,left.root,right.root);
left.root=right.root=NULL;
}
template<class T>
void BinaryTree<T>::BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right)
{
if(root||&left==&right||left.root==right.root) return;
x=root->element;
left.root=root->lChild;right.root=root->rChild;
delete root;root=NULL;//
}
template<class T>
void BinaryTree<T>::PreOrder(BTNode<T>* current)
{
loop:
while(current){
Visit(current->element);
if(current->rChild)
BTNode<T>::s.push(current->rChild);
current=current->lChild;
}
current=BTNode<T>::s.top();Visit(current->element);BTNode<T>::s.pop();
if(BTNode<T>::s.empty()) return;
else goto loop;
}
template<class T>
void BinaryTree<T>::PreOrder()
{
if(root)
PreOrder(root);
if(root->rChild)
PreOrder(root->rChild);
}