标题:二叉树层序遍历与递归
只看楼主
草种的幸福
Rank: 1
来 自:湖南
等 级:新手上路
帖 子:7
专家分:5
注 册:2012-11-2
 问题点数:0 回复次数:0 
二叉树层序遍历与递归
二叉树层序遍历用队列实现,可同递归算法一同实现怎么弄,此代码有问题,希望高手指教
#include<iostream>
using namespace std;
const int MaxSize=50;
template<class T>
struct Node
    {
        T data;
        Node<T> *lchild,*rchild;

    };
template<class T>
class BiTree
{
    public:
    BiTree(){root=Creat(root);}//通过递归返回最后一个节点,每次返回栈顶的元素,最后返回根节点
    ~BiTree(){Release(root);}
    void PreOrder(){PreOrder(root);}
    void InOrder(){InOrder(root);}
    void PostOrder(){PostOrder(root);}
    void LeverOrder();
    private:
    Node<T> Q[MaxSize];
    Node<T>*root;
    Node<T>*Creat(Node<T>*bt);
    void Release(Node<T>*bt);
    void PreOrder(Node<T>*bt);
    void InOrder(Node<T>*bt);
    void PostOrder(Node<T>*bt);
    //void LeverOrder(Node<T>*bt);
};

template<class T>
Node<T>*BiTree<T>::Creat(Node<T>*bt)//递归是通过堆栈而实现的
{
    T ch;
    cin>>ch;
    if(ch=='#') bt=NULL;
    else
    {
        bt=new Node<T>;
        bt->data=ch;
        bt->lchild=Creat(bt->lchild);//先生成左子树
        bt->rchild=Creat(bt->rchild);//再生成右子树
    }
    return bt;
}
template<class T>
void BiTree<T>::Release(Node<T>*bt)
{
    if(bt!=NULL)
    {
        Release(bt->lchild);
        Release(bt->rchild);
        delete bt;
    }
}
template<class T>
void BiTree<T>::PreOrder(Node<T>*bt)
{
    if(bt)
    {
        cout<<bt->data;
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}
template<class T>
void BiTree<T>::InOrder(Node<T>*bt)
{
    if(bt)
    {
        InOrder(bt->lchild);
        cout<<bt->data;
        InOrder(bt->rchild);
    }
}
template<class T>
void BiTree<T>::PostOrder(Node<T>*bt)
{
    if(bt)
    {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        cout<<bt->data;
    }
}
template<class T>
void BiTree<T>::LeverOrder()
{
    //Node<T> Q[MaxSize];
    int front=-1;
    int rear=-1;
    if(root==NULL)throw "error";
    Q[++rear]=root;
    if(front!=rear)
    {
        Node<T>* q=Q[++front];
        cout<<q->data;
        if(q->lchild!=NULL) Q[++rear]=q->lchild;
        if(q->rchild!=NULL) Q[++rear]=q->rchild;
    }


}
int main()
{
    try
    {
    BiTree<char> b;
    cout<<"二叉树的前序遍历:";
    b.PostOrder();
    cout<<endl;
    cout<<"二叉树的中序遍历:";
    b.InOrder();
    cout<<endl;
    cout<<"二叉树的后序遍历:";
    b.PostOrder();
    cout<<"二叉树的层次遍历:";
    b.LeverOrder();
    }catch(const char *e)
    {
        cout<<e<<endl;
    }

}
搜索更多相关主题的帖子: void 希望 include public 二叉树 
2012-12-06 13:43



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-389872-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.071084 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved