新建 文本文档.txt

二叉树的基本实现

#include<iostream.h>
#include<stdlib.h>
template<class T>
struct BTNode
{
    T data;
    BTNode<T> *lChild,*rChild;
    BTNode();
    BTNode(const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NULL)
{
        data=val;
        lChild=Childl;
        rChild=Childr;
}
    BTNode<T>* CopyTree()
{
        BTNode<T> *nl,*nr,*nn;
        if(&data==NULL)
            return NULL;
        nl=lChild->CopyTree();
        nr=rChild->CopyTree();
        nn=new BTNode<T>(data,nl,nr);
        return nn;
}
};
template<class T>
BTNode<T>::BTNode()
{
    lChild=rChild=NULL;
}
template<class T>
class BinaryTree
{
    public:
    BTNode<T> *root;
    BinaryTree();
    ~BinaryTree();
    void Pre_Order();
    void In_Order();
    void Post_Order();
    int TreeHeight()const;
    int TreeNodeCount()const;
    void DestroyTree();
    BTNode<T>* MakeTree(const T &element,BTNode<T> *l,BTNode<T> *r)
{
        root=new BTNode<T>(element,l,r);
     if(root==NULL)
   {
    cout<<"申请存贮地址失败，系统将关闭进程"<<endl;
    exit(1);
   }
   return root;
}
    private:
void Destroy(BTNode<T> *&r);
void PreOrder(BTNode<T> *r);
void InOrder(BTNode<T> *r);
void PostOrder(BTNode<T> *r);
int Height(const BTNode<T> *r)const;
int NodeCount(const BTNode<T> *r)const;
};
template<class T>
BinaryTree<T>::BinaryTree()
{
root=NULL;
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
DestroyTree();
}
template<class T>
void BinaryTree<T>::Pre_Order()
{
PreOrder(root);
}
template<class T>
void BinaryTree<T>::In_Order()
{
InOrder(root);
}
template<class T>
void BinaryTree<T>::Post_Order()
{
PostOrder(root);
}
template<class T>
int BinaryTree<T>::TreeHeight()const
{
return Height(root);
}
template<class T>
int BinaryTree<T>::TreeNodeCount()const
{
return NodeCount(root);
}
template<class T>
void BinaryTree<T>::DestroyTree()
{
Destroy(root);
}
template<class T>
void BinaryTree<T>::PreOrder(BTNode<T> *r)
{
    if(r!=NULL)
{
   cout<<r->data<<' ';
   PreOrder(r->lChild);
   PreOrder(r->rChild);
}
}
template<class T>
void BinaryTree<T>::InOrder(BTNode<T> *r)
{
if(r!=NULL)
{
   InOrder(r->lChild);
   cout<<r->data<<' ';
   InOrder(r->rChild);
}
}
template<class T>
void BinaryTree<T>::PostOrder(BTNode<T> *r)
{
if(r!=NULL)
{
   PostOrder(r->lChild);
   PostOrder(r->rChild);
   cout<<r->data<<' ';
}
}
template<class T>
int BinaryTree<T>::NodeCount(const BTNode<T> *r)const
{
if(r==NULL)
   return 0;
else
   return 1+NodeCount(r->lChild)+NodeCount(r->rChild);
}
template<class T>
int BinaryTree<T>::Height(const BTNode<T> *r)const
{
if(r==NULL)
   return 0;
else
{
   int lh,rh;
   lh=Height(r->lChild);
   rh=Height(r->rChild);
   return 1+(lh>rh?lh:rh);
}
}
template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r)
{
if(r!=NULL)
{
   Destroy(r->lChild);
   Destroy(r->rChild);
   delete r;
   r=NULL;
}
}
template<class T>
void Change(BTNode<T> *r)//将二叉树bt所有结点的左右子树交换
{
BTNode<T> *p;
if(r)
{ 
   p=r->lChild;
   r->lChild=r->rChild;
   r->rChild=p; //左右子女交换
   Change(r->lChild); //交换左子树上所有结点的左右子树
   Change(r->rChild); //交换右子树上所有结点的左右子树
}
}
void main()
{
BTNode<char> *b,*c,*d,*e,*f,*g;
BinaryTree<char> a;
b=a.MakeTree('F',NULL,NULL);
c=a.MakeTree('E',NULL,NULL);
d=a.MakeTree('D',NULL,NULL);
e=a.MakeTree('C',b,NULL);
f=a.MakeTree('B',d,c);
g=a.MakeTree('A',f,e);
cout<<"前序遍历:";
a.Pre_Order();
cout<<endl;
cout<<"中序遍历:";
a.In_Order();
cout<<endl;
cout<<"后序遍历:";
a.Post_Order();
cout<<endl;
cout<<"树的高度是:";
cout<<a.TreeHeight();
cout<<endl;
cout<<"树的结点个数是:";
cout<<a.TreeNodeCount();
cout<<endl<<endl;
cout<<"交换二叉树左右子树后，重新操作的结果是:"<<endl;

Change(a.root);//交换函数

cout<<"前序遍历:";
a.Pre_Order();
cout<<endl;
cout<<"中序遍历:";
a.In_Order();
cout<<endl;
cout<<"后序遍历:";
a.Post_Order();
cout<<endl;
cout<<"树的高度是:";
cout<<a.TreeHeight();
cout<<endl;
cout<<"树的结点个数是:";
cout<<a.TreeNodeCount();
cout<<endl<<endl;
}