注册 登录
编程论坛 数据结构与算法

关于二叉树的操作

发布于 2010-05-06 15:53, 628 次点击
#include <iostream>
#include<string>
using namespace std;
template <class T>
struct BiNode   
{
  T data;      
  BiNode<T> *lchild, *rchild;
};

template <class T>
class BiTree
{
public:
    BiTree(BiNode<T>*root);
    ~BiTree();
    BiNode<T>* Getroot();
    void PreOrder(BiNode<T>*root);
    void NpreOrder(BiNode<T>*root);
    void InOrder(BiNode<T>*root);
    void PostOrder(BiNode<T>*root);
    void LevelOrder(BiNode<T>*root);
private:
    BiTree<T>*root;
    void Creat(BiNode<T>*root);
    void Release(BiNode<T>*root);
};


template<class T>   //构造树
BiTree<T>::BiTree(BiNode<T>*root)
{
    Creat(root);
}
template <class T>
void BiTree<T>::Creat(BiNode<T>*root)
{
    T ch;
    cout<<"请输入创建一棵二叉树的结点数据"<<endl;
    cin>>ch;
    if(ch=="#")root=NULL;
    else{
        root=new BiNode<T>;
        root->data=ch;
        Creat(root->lchild);
        Creat(root->rchild);
    }
}
template <class T>  //析构树
BiTree<T>::~BiTree()
{
    Release(root);
}
template<class T>
void BiTree<T>::Release(BiNode<T>*root)
{
    if(root!=NULL){
        Release(root->lchild);
        Release(root->rchild);
        delete root;
    }
}

template<class T>    //得到树顶
BiNode<T>* BiTree<T>::Getroot( )
{
    return root;
}

//树的遍历算法

template <class T>          //前序递归算法
void BiTree<T>::PreOrder(BiNode<T>*root)
{
    if(root==NULL) return;
    else{
        cout<<root->data;
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

template <class T>        //前序非递归算法
void BiTree<T>::NpreOrder(BiNode<T>*root)
{
    top=-1;
    while(root!=NULL||top!=-1)
    {
        while(root!=NULL)
        {
        cout<<root->data;
        s[++top]=root;
        root=root->lchild;
    }
    if(top!=-1){
        root=s[top--];
        root=root->rchild;
    }
}
}
template<class T>      //中序递归算法
void BiTree<T>::InOrder(BiNode<T>*root)
{
    if(root==NULL) return;
    else{
        InOrder(root->lchild);
        cout<<root->data;
        InOrder(root->rchild);
    }
}
template <class T>    //后序递归算法
void BiTree<T>::PostOrder(BiNode<T>*root)
{
    if(root==NULL) return;
    else{
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        cout<<root->data;
    }
}
template<class T>    //层序遍历算法
void BiTree<T>::LevelOrder(BiNode<T>*root)
{
    const int MaxSize = 100;
    int front;
    int rear;
    BiNode<T> *q;
    BiNode<T> *Q[MaxSize]
    front=rear=0;
    if(root==NULL) return;
    Q[++rear]=root;
    while(front!=rear)
    {
        q=Q[++front];
        cout<<q->data;
        if(q->lchild!=NULL) Q[++rear]=q->lchild;
        if(q->rchild!=NULL) Q[++rear]=q->rchild;
    }
}

void main()
{
    BiTree<string> tree;
    BiNode<string>* root = tree.Getroot( );
    cout<<"------前序遍历------ "<<endl;
    tree.PreOrder(root);
    cout<<endl;
    cout<<"------前序非递归遍历------ "<<endl;
    tree.NpreOrder(root);
    cout<<"------中序遍历------ "<<endl;
    tree.InOrder(root);
    cout<<endl;
    cout<<"------后序遍历------ "<<endl;
    tree.PostOrder(root);
    cout<<endl;
    cout<<"------层序遍历------ "<<endl;
    tree.LevelOrder(root);
    cout<<endl;
}
出了一点小问题,实在是找不出来了,希望哪位高手能帮帮忙!
下面是问题的提示,我看不懂,希望能解释一下是什么意思,谢谢了!
e:\study\vc程序\vc++\树的操作.cpp(143) : error C2512: 'BiTree<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >' : no appropriate default constructor available
执行 cl.exe 时出错.

树的操作.exe - 1 error(s), 0 warning(s)
3 回复
#2
hzh5122010-05-06 21:36
程序有太多不合理的地方。
给出改后的程序,你自己慢慢领会吧!
测试用例:A B C # # D E # G # # F # # #

程序代码:
#include <iostream>
#include<string>
using namespace std;
template <class T>
struct BiNode
{

 T data;   

 BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:

 BiTree(){ }  // 构造函数 重载后,就取消默认构造函数
BiTree(BiNode<T>*root);

 ~BiTree();

 BiNode<T>* Getroot();

 void PreOrder(BiNode<T>*root);

 void NpreOrder(BiNode<T>*root);

 void InOrder(BiNode<T>*root);

 void PostOrder(BiNode<T>*root);

 void LevelOrder(BiNode<T>*root);
private:

 BiNode<T> *root;

 BiNode<T>* Creat(BiNode<T>*root);

 void Release(BiNode<T>*root);
};

template<class T>   //构造树
BiTree<T>::BiTree(BiNode<T>*root)
{

 cout<<"请输入创建一棵二叉树的结点数据"<<endl;

 this->root=Creat(root);
}

template <class T>
BiNode<T>* BiTree<T>::Creat(BiNode<T>*root)
{

 T ch;

 cin>>ch;

 if(ch=="#")
  root=NULL;

 else{
  root=new BiNode<T>;
  root->data=ch;
  root->lchild=Creat(root->lchild);
  root->rchild=Creat(root->rchild);

 }

 return root;
}
template<class T>
void BiTree<T>::Release(BiNode<T>*root)
{

 if(root!=NULL){
  Release(root->lchild);
  Release(root->rchild);
  delete root;

 }
}
template <class T>  //析构树
BiTree<T>::~BiTree()
{

 Release(root);
}
template<class T>    //得到树顶
BiNode<T>* BiTree<T>::Getroot( )
{

 return root;
}
//树的遍历算法
template <class T>          //前序递归算法
void BiTree<T>::PreOrder(BiNode<T>*root)
{

 if(root==NULL) return;

 else{
  cout<<root->data;
  PreOrder(root->lchild);
  PreOrder(root->rchild);

 }
}
/*
template <class T>        //前序非递归算法 程序有语法错误,自己改正吧
void BiTree<T>::NpreOrder(BiNode<T>*root)
{

 top=-1;

 while(root!=NULL||top!=-1)

 {
  while(root!=NULL)
  {
   cout<<root->data;
   s[++top]=root;
   root=root->lchild;
  }
  if(top!=-1){
   root=s[top--];
   root=root->rchild;
  }

 }
}
*/
template<class T>      //中序递归算法
void BiTree<T>::InOrder(BiNode<T>*root)
{

 if(root==NULL) return;

 else{
  InOrder(root->lchild);
  cout<<root->data;
  InOrder(root->rchild);

 }
}
template <class T>    //后序递归算法
void BiTree<T>::PostOrder(BiNode<T>*root)
{

 if(root==NULL) return;

 else{
  PostOrder(root->lchild);
  PostOrder(root->rchild);
  cout<<root->data;

 }
}
template<class T>    //层序遍历算法
void BiTree<T>::LevelOrder(BiNode<T>*root)
{

 const int MaxSize = 100;

 int front;

 int rear;

 BiNode<T> *q;

 BiNode<T> *Q[MaxSize];

 front=rear=0;

 if(root==NULL) return;

 Q[++rear]=root;

 while(front!=rear)

 {
  q=Q[++front];
  cout<<q->data;
  if(q->lchild!=NULL) Q[++rear]=q->lchild;
  if(q->rchild!=NULL) Q[++rear]=q->rchild;

 }
}
int main()
{

 BiTree<string> tree(NULL);

 BiNode<string>* root = tree.Getroot( );

 cout<<"------前序遍历------ "<<endl;

 tree.PreOrder(root);

 cout<<endl;

 cout<<"------前序非递归遍历------ "<<endl;
// tree.NpreOrder(root);
cout<<"------中序遍历------ "<<endl;

 tree.InOrder(root);

 cout<<endl;

 cout<<"------后序遍历------ "<<endl;

 tree.PostOrder(root);

 cout<<endl;

 cout<<"------层序遍历------ "<<endl;

 tree.LevelOrder(root);

 cout<<endl;

 return 0;
}

#3
2010-05-06 22:38
this在这里是什么意思呢?
template<class T>   //构造树
BiTree<T>::BiTree(BiNode<T>*root)
{
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
this->root=Creat(root);
}
还有这句BiNode<T>* Creat(BiNode<T>*root);为什么把Create声明为BiNode<T>的呢?很是不解啊?谢谢帮助!
#4
2010-05-07 01:41
BiTree<T>::BiTree(BiNode<T>*root) 是带有参数的构造函数。里面的this是指代当前创建的对象。
二叉树的节点都是是结构体,然后用二叉链表链接起来的,所以树的根节点也是一个结构体。

1