踏月光
2017-11-13 06:55
采纳率: 100%
浏览 1.5k
已采纳

数据结构中二叉树的应用

这个代码是老师给的,但是里面那个字符数组我不是很懂,请问这个的主函数怎么写?图片

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • weixin_40346192 2017-11-13 14:15
    已采纳

    有两种方法递归和非递归
    二叉树遍历递归:
    =====================================main============================
    #include
    #include "Bitree.h"
    using namespace std;
    bool PrintElement(char e)
    {
    cout< return true;
    }
    int main()
    {
    BiTree T;
    BiTNode *r=T.GetRoot();
    T.CreateBiTree(r);

    T.SetRoot(r);
    cout<<"先序遍历序列为:";

    T.PreOrderTraverse(r ,PrintElement);
    cout<<"\n中序遍历序列为: ";

    T.InOrderTraverse(r ,PrintElement);
    cout<<"\n后序遍历序列为: ";
    T.PostOrderTraverse(r ,PrintElement);
    return 0;
    }

    ==================================Bitree.h===================================
    #include
    using namespace std;
    struct BiTNode
    {

    char data ;
    struct BiTNode lchild , *rchild ;
    };
    template
    class BiTree
    {
    public:
    BiTree();

    void CreateBiTree(BiTNode
    &SubTree);
    bool PreOrderTraverse(BiTNode* &SubTree,bool(* Visit)(TElemType e));
    bool InOrderTraverse(BiTNode* &SubTree,bool(* Visit)(TElemType e));
    bool PostOrderTraverse(BiTNode* &SubTree,bool(* Visit)(TElemType e));
    BiTNode GetRoot(){ return root;}
    void SetRoot(BiTNode * &SubTree){ root=SubTree;}
    private:

    BiTNode
    root;
    };

    template
    BiTree::BiTree() //建空的二叉树
    {
    root = NULL;
    }
    template
    void BiTree::CreateBiTree(BiTNode* &SubTree)
    {
    char ch;
    cin>>ch;
    if(ch == '*') SubTree=NULL;
    else
    {
    SubTree = new BiTNode;
    SubTree->data=ch;
    CreateBiTree( SubTree->lchild );
    CreateBiTree( SubTree->rchild );

    }

    }

    template
    bool BiTree:: PreOrderTraverse (BiTNode* &SubTree,bool(* Visit)(TElemType e))
    {
    if(SubTree){
    if( Visit(SubTree->data) )
    if( PreOrderTraverse( SubTree->lchild ,Visit) )
    if( PreOrderTraverse( SubTree->rchild ,Visit) )
    return true;
    cout<<"ERROR";
    }else return true;

    } //PreOrderTraverse先序遍历,递归

    template
    bool BiTree:: InOrderTraverse ( BiTNode* &SubTree,bool(* Visit)(TElemType e))
    {
    if( SubTree ){
    if( InOrderTraverse( SubTree->lchild ,Visit) )
    if( Visit(SubTree->data) )
    if( InOrderTraverse( SubTree->rchild ,Visit) )
    return true;
    cout<<"ERROR";
    }else return true;

    } //InOrderTraverse中序遍历,递归

    template
    bool BiTree:: PostOrderTraverse (BiTNode* &SubTree,bool(* Visit)(TElemType e))
    {
    if(SubTree){
    if( PostOrderTraverse( SubTree->lchild ,Visit) )
    if( PostOrderTraverse( SubTree->rchild ,Visit) )
    if( Visit(SubTree->data) )

    return true;
    cout<<"ERROR";
    }else return true;

    }//PostOrderTraverse后序遍历,递归

    二叉树遍历非递归:
    ============================================main============================================
    #include
    #include "Bitree.h"
    using namespace std;
    bool PrintElement(char e)
    {
    cout< return true;
    }
    int main()
    {
    BiTree T;
    BiTNode *r=T.Getroot();
    T.CreateBiTree(r);
    T.SetRoot(r);
    cout<<"先序非递归遍历序列为:";

    T.NonRecurPreOrder(PrintElement);

    cout<<"\n中序非递归遍历序列为: ";

    T.NonRecurInOrder(PrintElement);
    cout<<"\n后序非递归遍历序列为: ";
    T.NonRecurPostOrder(PrintElement);
    return 0;
    }
    =======================================SqStack.h===============================
    #include
    using namespace std;
    template
    class SqStack
    {
    protected:
    // 顺序栈的数据成员:
    int count; // 元素个数
    int maxSize; // 栈最大元素个数
    ElemType *elems; // 元素存储空间
    public:
    // 抽象数据类型方法声明及重载编译系统默认方法声明:
    SqStack(int size=8); // 构造函数模板
    virtual ~SqStack(); // 析构函数模板

    void Push(ElemType &e); // 入栈
    ElemType Pop(ElemType &e); // 出栈

    bool Empty();

    };

    // 顺序栈类模板的实现部分

    template
    SqStack::SqStack(int size)
    // 操作结果:构造一个最大元素个数为size的空栈
    {
    elems = NULL; // 未分配存储空间前,elems为空
    maxSize = size;// 最大元素个数 // 释放存储空间
    if (elems != NULL) delete []elems;
    elems = new ElemType[maxSize]; // 分配存储空间
    count = 0;
    }

    template
    SqStack::~SqStack()
    // 操作结果:销毁栈
    {
    delete []elems; // 释放存储空间
    }

    template
    void SqStack::Push(ElemType &e)
    // 操作结果:将元素e追加到栈顶,如成功则返加SUCCESS,如栈已满将返回OVER_FLOW
    {
    if (count == maxSize)
    { // 栈已满
    cout<<"OVER_FLOW";
    }
    else
    { // 操作成功
    elems[count++] = e; // 将元素e追加到栈顶

    }
    }

    template
    ElemType SqStack::Pop(ElemType &e)
    // 操作结果:如栈非空,删除栈顶元素,并用e返回栈顶元素,返回SUCCESS,否则
    // 返回UNDER_FLOW
    {
    if (count == 0)
    { // 栈空
    cout<<"UNDER_FLOW";
    return false;
    }
    else
    { // 操作成功
    e = elems[count - 1]; // 用e返回栈顶元素
    count--;

    return e;
    }
    }

    template
    bool SqStack::Empty()
    // 操作结果:如栈为空,则返回true,否//则返回false
    {
    return count == 0;
    }

    ====================================Bitree.h===================================
    #include
    #include "SqStack.h"
    using namespace std;
    struct BiTNode
    {

    char data ;
    struct BiTNode lchild , *rchild ;
    bool rightSubTreeVisited;
    };
    template
    class BiTree
    {
    public:
    BiTree();

    void CreateBiTree(BiTNode *&SubTree);
    BiTNode * Getroot(){ return root;}
    void SetRoot(BiTNode * &SubTree){ root=SubTree;}
    bool BiTree::NonRecurPreOrder(bool(
    Visit)(TElemType e));
    bool BiTree::NonRecurInOrder(bool(* Visit)(TElemType e));
    bool BiTree::NonRecurPostOrder(bool(* Visit)(TElemType e));
    private:

    BiTNode* root;
    };

    template
    BiTree::BiTree() //建空的二叉树
    {
    root = NULL;
    }

    template
    void BiTree::CreateBiTree(BiTNode &SubTree)
    {
    char ch;
    cin>>ch;
    if(ch == '
    ') SubTree=NULL;
    else
    {
    SubTree = new BiTNode;
    SubTree->data=ch;
    CreateBiTree( SubTree->lchild );
    CreateBiTree( SubTree->rchild );

    }

    }

    template
    bool BiTree::NonRecurPreOrder(bool(* Visit)(TElemType e))
    {
    SqStack S;
    BiTNode* p;
    p = root;

    while( p || !S.Empty())
    {

    if(p)
    { //遇到一个结点

            if( !Visit(p->data) ) 
                return false;  //访问结点
            S.Push(p);  //压入堆栈 
            p=p->lchild;    //进入左子树     
        }
        else
        {
            S.Pop(p);
            p=p->rchild;
        }           
    }
    return true;
    

    }

    template
    bool BiTree::NonRecurInOrder(bool(* Visit)(TElemType e))
    {
    SqStack S;
    BiTNode* p;
    p = root;

    while( p || !S.Empty())
    {
        if(p) 
        {
            S.Push(p);
            p = p->lchild;
        } 
        else
        {
            S.Pop(p);
            if( !Visit(p->data) ) return false;  //访问结点 
            p=p->rchild;
        }
    } //while
    return true;    
    

    }

    template
    bool BiTree::NonRecurPostOrder(bool(* Visit)(TElemType e))
    {
    SqStack S;
    BiTNode* p;
    p = root;

    while( p || !S.Empty())
    {
    while(p)
    { //找到最左的结点
    S.Push(p);
    p=p->lchild;
    }
    S.Pop(p);
    while( p->rightSubTreeVisited==true )
    { //右子树已遍历
    if( !Visit(p->data) ) return false; //访问结点
    if( !S.Empty() )
    {
    S.Pop(p);
    }
    else
    {

    return true;

    }
    }
    //右子树未遍历,遍历右子树
    p->rightSubTreeVisited=true;
    S.Push(p); /*很重要*/
    p=p->rchild;

    }
    return true;

    }

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • 踏月光 2017-11-13 14:35

    就我发的那个而言,主函数应该怎么写呢?

    评论
    解决 无用
    打赏 举报
  • weixin_40346192 2017-11-14 16:29

    你参照下我的void main()去改啊

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题