fangdongheiha
Celia_D
采纳率41.2%
2019-11-26 16:12

二叉树非递归前序遍历

已采纳

实在看不出来有啥毛病了,请各位大佬帮忙看一下!

图片说明

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
using namespace std;
#define N 100
extern char *a;     /*存放扩充二叉树的前序序列*/
char *a="ABC##D#E##F##";  /*扩充二叉树序树t的前序序列*/

typedef struct node /*二叉树结构定义*/
{
    char data;
    struct node *lchild,*rchild;
}binnode;
typedef binnode *bintree;

/*函数creatbintree (根据扩充二叉树的前序序列(字符串a)建立二叉树t的存储结构*/
bintree creatbintree()
{

    char ch=*a++;
    bintree t;
    if  (ch=='#')  
        t=NULL;
    else
    { t=(bintree)malloc(sizeof(binnode));
      t->data=ch;
      t->lchild=creatbintree();
      t->rchild=creatbintree();
    }
    return t;
}

void preorder(bintree t)  /*前序递归遍历二叉树*/
{
    if (t)
    {
        printf("%c",t->data);
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
void postorder(bintree t)  /*后序递归遍历二叉树*/
{
    if (t)
    {

        postorder(t->lchild);
        postorder(t->rchild);
        printf("%c",t->data);
    }
}

/*顺序栈定义*/
typedef struct
{
    bintree data[N];
    int top;
    int tag[N];
}seqstack;

void init(seqstack *s)   /*初始化空栈*/
{
    s->top=-1;
}
int empty(seqstack *s)   /*判断栈是否为空*/
{
    if (s->top>-1) return 0;
    else return 1;
}
int full(seqstack *s)   /*判断栈是否为满*/
{
    if (s->top==N-1) return 1;
    else return 0;
}
void push(seqstack *s ,bintree x)   /*进栈*/
{
    if (!full(s))
        s->data[++s->top]=x;
}
bintree pop(seqstack *s)            /*出栈*/
{
    if (!empty(s))
        return s->data[s->top--];
}

bintree top(seqstack *s)
{
    if(empty(s))
        return s->data[s->top];
}

/*函数preorder1()的功能是非递归前序遍历二叉树t*/
void preorder1(bintree t)
{
    seqstack *s;
    init(s);
    bintree p=t;
    while(!empty(s)||p)
    {
        if(p)
        {
            cout<<p->data;
            push(s,p);
            p=p->lchild;
        }
        else
        {
            p=top(s);
            pop(s);
            p=p->rchild;
        }
    }
    cout<<endl;

}
int _tmain(int argc, _TCHAR* argv[])
{

    bintree t;
    t=creatbintree();   /*建立二叉树t的存储结构*/
    printf("二叉树的前序序列为:\n");
    preorder1(t);       /*前序非递归遍历二叉树*/
    return 0;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

4条回答

  • zz00217 空白如空 2年前
    
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    #define N 100
    extern char *a;     /*存放扩充二叉树的前序序列*/
    char *a="ABC##D#E##F##";  /*扩充二叉树序树t的前序序列*/
    
    typedef struct node /*二叉树结构定义*/
    {
        char data;
        struct node *lchild,*rchild;
    }binnode;
    typedef binnode *bintree;
    
    /*函数creatbintree (根据扩充二叉树的前序序列(字符串a)建立二叉树t的存储结构*/
    bintree creatbintree()
    {
    
        char ch=*a++;
        bintree t;
        if  (ch=='#')  
            t=NULL;
        else
        { t=(bintree)malloc(sizeof(binnode));
          t->data=ch;
          t->lchild=creatbintree();
          t->rchild=creatbintree();
        }
        return t;
    }
    
    void preorder(bintree t)  /*前序递归遍历二叉树*/
    {
        if (t)
        {
            printf("%c",t->data);
            preorder(t->lchild);
            preorder(t->rchild);
        }
    }
    void postorder(bintree t)  /*后序递归遍历二叉树*/
    {
        if (t)
        {
    
            postorder(t->lchild);
            postorder(t->rchild);
            printf("%c",t->data);
        }
    }
    
    /*顺序栈定义*/
    typedef struct
    {
        bintree data[N];
        int top;
        int tag[N];
    }seqstack;
    
    void init(seqstack *s)   /*初始化空栈*/
    {
        s->top=-1;
    }
    int empty(seqstack *s)   /*判断栈是否为空*/
    {
        if (s->top>-1) return 0;
        else return 1;
    }
    int full(seqstack *s)   /*判断栈是否为满*/
    {
        if (s->top==N-1) return 1;
        else return 0;
    }
    void push(seqstack *s ,bintree x)   /*进栈*/
    {
        if (!full(s))
            s->data[++s->top]=x;
    }
    bintree pop(seqstack *s)            /*出栈*/
    {
        if (!empty(s))
            return s->data[s->top--];
    }
    
    bintree top(seqstack *s)
    {
        if(!empty(s))  //修改位置
            return s->data[s->top];
    }
    
    /*函数preorder1()的功能是非递归前序遍历二叉树t*/
    void preorder1(bintree t)
    {
        seqstack *s = new seqstack(); //修改位置
        init(s);
        bintree p=t;
        while(!empty(s)||p)
        {
            if(p)
            {
                cout<<p->data;
                push(s,p);
                p=p->lchild;
            }
            else
            {
                p=top(s);
                pop(s);
                p=p->rchild;
            }
        }
        cout<<endl;
    
    }
    int main()
    {
    
        bintree t;
        t=creatbintree();   /*建立二叉树t的存储结构*/
        printf("二叉树的前序序列为:\n");
        preorder1(t);       /*前序非递归遍历二叉树*/
    //    return 0;
    }
    
    点赞 评论 复制链接分享
  • ZL1599292797 QiQaWgYu 2年前

    指针用的太乱了,好多地方用错了

    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    #define N 100
    extern char* a;     /*存放扩充二叉树的前序序列*/
    char* a = "ABC##D#E##F##";  /*扩充二叉树序树t的前序序列*/
    
    typedef struct node /*二叉树结构定义*/
    {
        char data;
        struct node* lchild, * rchild;
    }binnode;
    typedef binnode* bintree;
    
    /*函数creatbintree (根据扩充二叉树的前序序列(字符串a)建立二叉树t的存储结构*/
    bintree creatbintree()
    {
    
        char ch = *a++;
        bintree t;
        if (ch == '#')
            t = NULL;
        else
        {
            t = (bintree)malloc(sizeof(binnode));
            t->data = ch;
            t->lchild = creatbintree();
            t->rchild = creatbintree();
        }
        return t;
    }
    
    void preorder(bintree t)  /*前序递归遍历二叉树*/
    {
        if (t)
        {
            printf("%c", t->data);
            preorder(t->lchild);
            preorder(t->rchild);
        }
    }
    void postorder(bintree t)  /*后序递归遍历二叉树*/
    {
        if (t)
        {
    
            postorder(t->lchild);
            postorder(t->rchild);
            printf("%c", t->data);
        }
    }
    
    /*顺序栈定义*/
    typedef struct
    {
        bintree data[N];
        int top;
        int tag[N];
    }seqstack;
    
    void init(seqstack* s)   /*初始化空栈*/
    {
        s->top = -1;
    }
    int empty(seqstack s)   /*判断栈是否为空*/
    {
        if (s.top > -1) return 0;
        else return 1;
    }
    int full(seqstack s)   /*判断栈是否为满*/
    {
        if (s.top == N - 1) return 1;
        else return 0;
    }
    void push(seqstack* s, bintree x)   /*进栈*/
    {
        if (!full(*s))
            s->data[++s->top] = x;
    }
    bintree pop(seqstack* s)            /*出栈*/
    {
        if (!empty(*s))
            return s->data[s->top--];
    }
    
    bintree top(seqstack* s)
    {
        if (!empty(*s))
            return s->data[s->top];
    }
    
    /*函数preorder1()的功能是非递归前序遍历二叉树t*/
    void preorder1(bintree t)
    {
        seqstack s;
        init(&s);
        bintree p = t;
        while (!empty(s) || p)
        {
            if (p)
            {
                cout << p->data;
                push(&s, p);
                p = p->lchild;
            }
            else
            {
                p = top(&s);
                pop(&s);
                p = p->rchild;
            }
        }
        cout << endl;
    
    }
    int main()
    {
    
        bintree t;
        t = creatbintree();   /*建立二叉树t的存储结构*/
        printf("二叉树的前序序列为:\n");
        preorder1(t);       /*前序非递归遍历二叉树*/
        return 0;
    }
    
    点赞 评论 复制链接分享
  • lx614happy lx614happy 2年前

    建议仔细看一下日志很清楚了,seqstack类型的指针s在使用的时候没有初始化,你只是声明了一个指针。

    点赞 评论 复制链接分享
  • Donald_Shallwing Donald_Shallwing 2年前
    点赞 评论 复制链接分享

相关推荐