#ifndef _ELLEN_H_
#define _ELLEN_H_
template<class T>class BinaryTree;
template<class T>
class BinaryTreeNode{
friend class BinaryTree<T>;
private:
BinaryTreeNode<T>* m_Left;
BinaryTreeNode<T>* m_right;
T element; //二叉树结点数据域
public:
BinaryTreeNode():element(0),m_Left(0),m_right(0){};
//缺省构造函数
BinaryTreeNode(const T&ele):element(ele),m_Left(0),m_right(0){};
//给定数据的构造函数
//给定了节点值和左右结点
BinaryTreeNode(const T&ele,BinaryTreeNode<T>*l,BinaryTreeNode<T>*r):
element(ele),m_Left(l),m_right(r){};
T value()const; //返回当前结点数据
BinaryTreeNode<T> * leftchild() const;//返回左子树
BinaryTreeNode<T> * rightchild() const;//返回右子树
void setLeftchild(BinaryTreeNode<T>*);//设置当前结点的左子树
void setRightchild(BinaryTreeNode<T>*);//设置当前结点的右子树
void setValue(const T&val);//设置当前结点的数据域
bool isLeaf()const;//判定当前结点是否为叶结点
//重载赋值操作符
BinaryTreeNode<T>&operator=(const BinaryTreeNode<T>&Node);
};
template<class T>//返回数据域
T BinaryTreeNode<T>::value()const
{
return element;
}
template<class T>//返回左结点
BinaryTreeNode<T>* BinaryTreeNode<T>::leftchild() const
{
return m_Left;
}
template<class T>//返回左结点
BinaryTreeNode<T>* BinaryTreeNode<T>::rightchild() const
{
return m_right;
}
template<class T>//设置左节点
void BinaryTreeNode<T>::setLeftchild(BinaryTreeNode<T>*l)
{
m_Left = l;
}
template<class T>//设置右结点
void BinaryTreeNode<T>::setRightchild(BinaryTreeNode<T>*r)
{
m_right = r;
}
template<class T>//设置数据域
void BinaryTreeNode<T>::setValue(const T &val)
{
element = val;
}
template<class T>//判断结点是否为树叶
bool BinaryTreeNode<T>::isLeaf()const
{
if (m_Left==NULL&&m_right==NULL)
return 0;
else
return 1;
}
template<class T>//赋值重载
BinaryTreeNode<T>&BinaryTreeNode<T>::operator=(const BinaryTreeNode<T>&Node)
{
if (this == &Node)
return *this;
delete this;
element = Node.element;
m_Left = Node.m_Left;
m_right = Node.m_right;
return *this;
}
template<class T>
class BinaryTree{
private:
BinaryTreeNode<T> *root;//二叉树根结点
//从二叉树的root结点开始，查找current结点的父结点
BinaryTreeNode<T>*GetParent(BinaryTreeNode<T> *root,BinaryTreeNode<T> *current);
public:
BinaryTree():root(0){};//构造函数
~BinaryTree(){DeleteBinaryTree(root);};//析构函数
bool isEmpty()const;//判断二叉树是否为空
BinaryTreeNode<T> *Root(){return root;};//返回根结点
BinaryTreeNode<T> *Parent(BinaryTreeNode<T>*current);//返回current的父结点
BinaryTreeNode<T> *LeftSibling(BinaryTreeNode<T>*current);//返回current的左兄弟
BinaryTreeNode<T> *RightSibling(BinaryTreeNode<T>*current);//返回current的右兄弟
//以elem为根结点，构造新的二叉树
void CreateTree(const T&elem,BinaryTree<T>&leftTree,BinaryTree<T>&rightTree);
void PreOrder(BinaryTreeNode<T>*root);//前序周游有二叉树或其子树
void InOrder(BinaryTreeNode<T>*root);//中序周游有二叉树或其子树
void PostOrder(BinaryTreeNode<T>*root);//后序周游有二叉树或其子树
//
void LevelOrder(BinaryTreeNode<T>*root);//按层次周游有二叉树或其子树
void DeleteBinaryTree(BinaryTreeNode<T>*root);//删除二叉树或其子树
};
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::GetParent(BinaryTreeNode<T> *root,BinaryTreeNode<T> *current)
{//找父节点
BinaryTreeNode<T>* temp;
if (root == NULL)
return NULL;
if((root->leftchild()==current)||(root->rightchild()==current))
return root;
if((temp=GetParent(root->leftchild(),current))!=NULL)
return temp;
else
return GetParent(root->leftchild(),current);
}
template<class T>//寻找父节点
BinaryTreeNode<T> * BinaryTree<T>::Parent(BinaryTreeNode<T>*current){
if((current == NULL)||(current == root))
return NULL;
return GetParent(root,current);
}
template<class T>//返回current的左兄弟
BinaryTreeNode<T> * BinaryTree<T>::LeftSibling(BinaryTreeNode<T>*current){
if(current)
{
BinaryTreeNode<T>*temp = Parent(current);
if((temp==NULL)||(temp->leftchild()==NULL))
return NULL;
else
return temp->leftchild();
}
return NULL;
}
template<class T>//返回current的右兄弟
BinaryTreeNode<T> * BinaryTree<T>::RightSibling(BinaryTreeNode<T>*current){
if(current)
{
BinaryTreeNode<T>*temp = Parent(current);
if((temp==NULL)||(temp->rightchild()==NULL))
return NULL;
else
return temp->rightchild();
}
return NULL;
}
template<class T>//创建新树
void BinaryTree<T>::CreateTree(const T&elem,BinaryTree<T> &leftTree,BinaryTree<T> &rightTree)
{
root = new BinaryTreeNode<T>(elem,leftTree.root,rightTree.root);
leftTree.root = rightTree.root = NULL;
}
template<class T>//删除模板
void BinaryTree<T>::DeleteBinaryTree(BinaryTreeNode<T>*root)
{
if (root)
{
DeleteBinaryTree(root->m_Left);
DeleteBinaryTree(root->m_right);
delete root;
}
}
template<class T>
void BinaryTree<T>::PreOrder(BinaryTreeNode<T>*root){//前序周游有二叉树或其子树
if (root!=NULL)
{
Root(root);
PreOrder(root->leftchild());
PreOrder(root->rightchild());
}
}
template<class T>
void BinaryTree<T>::InOrder(BinaryTreeNode<T>*root){//中序周游有二叉树或其子树
if (root!=NULL)
{
InOrder(root->leftchild());
Root(root);
InOrder(root->rightchild());
}
}
template<class T>
void BinaryTree<T>::PostOrder(BinaryTreeNode<T>*root){//后序周游有二叉树或其子树
if (root!=NULL)
{
PostOrder(root->leftchild());
PostOrder(root->rightchild());
Root(root);
}
}
//void BinaryTree<T>::LevelOrder(BinaryTreeNode<T>*root)
#endif
C++写的未完善的
2010-05-14 01:04
程序代码：
