Celia_D 2019-11-26 16:12 采纳率: 50%
浏览 574
已采纳

二叉树非递归前序遍历

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

图片说明

#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条回答 默认 最新

      报告相同问题?

      相关推荐 更多相似问题

      悬赏问题

      • ¥20 有人知道怎么将vsi格式的图片文件,转换为svs格式的文件吗
      • ¥15 历史模拟法计算var实验报告
      • ¥15 白鲸算法优化K值的VMD分解出错
      • ¥20 写一个基于52单片机用hc-05蓝牙模块控制28BYJ-48步进电机进行旋转,在手机蓝牙串口输入1019电机转半圈,输入2038电机转一圈,输入0复位的代码吗
      • ¥15 求51单片机8位数码管计时器程序
      • ¥20 matlab识别螺母边缘
      • ¥15 python 6x6游戏加登录、记录系统
      • ¥100 基于做一个模拟智慧路灯
      • ¥15 ME21N 创建采购成功并且生成采购订单号,但显示“快件文档更新已取消”,SM13看错误提示为如下截图:
      • ¥30 android 集成fmod实现变声功能中遇到的问题