取名字好难-_- 2022-05-12 21:42 采纳率: 58.3%
浏览 336
已结题

二叉树非递归遍历算法

栈及二叉树的非递归遍历
本题要求根据相关数据类型的定义,写出相关的函数实现,包括:

栈的初始化函数、取栈顶元素,栈是否为空,push和pop函数由裁判程序给出,无需再写。
二叉树的先序遍历函数和中序遍历函数,要求使用非递归算法。后序遍历的非递归算法由裁判程序给出,无需再写。
函数接口定义:

在这里描述函数接口:
#include <iostream>
#define MAXSIZE 100 //顺序栈存储控件的初始分配量
#define OK 1
#define ERROR 0
#define OVERFLOW -1
using namespace std;
typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
    TElemType Data;
    struct BiTNode *lchild,*rchild;
    int flag;//用于非递归后序遍历
}BiTNode,*BiTree;

static int pushCount = 0; //用于统计入栈的次数
static int popCount = 0; //用于统计出栈的次数

/*------------------------顺序栈的定义---------------------*/
typedef BiTNode* SElemType;//栈中存储的是结点的指针而非结点本身
typedef struct{
    SElemType *base;//栈底指针
    SElemType *top; //栈顶指针
    int stacksize;  //栈可用的最大容量
}SqStack;

/*栈的实现 */
//下面两个函数由裁判程序实现,无需再写
Status Push(SqStack &S,SElemType e);/*元素e入栈*/
Status Pop(SqStack &S,SElemType &e);/* 删除并仅返回S的栈顶元素 */

//下面三个函数请提供实现代码
Status InitStack(SqStack &S);  /*栈初始化 */
SElemType GetTop(SqStack S);    /* 仅返回S的栈顶元素 */
bool stackEmpty(SqStack S);   /*栈是否为空,为空则返回true,否则返回false*/
/*--------------------------堆栈的定义结束------------------*/

//下面三个函数请提供实现代码
void CreateBiTree(BiTree& BT);//先序遍历的顺序建立二叉链表
void InorderTraverse( BiTree BT );//非递归中序遍历
void PreorderTraverse( BiTree BT );//非递归先序遍历
//下面函数由裁判程序实现,无需提供实现代码
void PostorderTraverse( BiTree BT );//非递归后序遍历
void TestStack();
void CreateBiTree1(BiTree& BT);

裁判测试程序样例:
在这里给出函数被调用进行测试:
int main()
{
    BiTree BT;
    int mode ;
    cin>>mode;
    switch(mode){
        case 0: //测试栈的相关函数定义
            TestStack();break;
        case 1: //测试CreateBiTree()函数
            CreateBiTree(BT);
            cout<<"Postorder:";
            PostorderTraverse(BT);
            cout<<endl;
            break;
        case 2: //测试PreorderTraverse()函数
            CreateBiTree1(BT);
            pushCount = popCount = 0;
            cout<<"Preorder:"; PreorderTraverse(BT); cout<<endl;
            cout<<"pushCount:"<<pushCount<<endl;
            cout<<"popCount:"<<popCount<<endl;
            break;
        default: //测试InorderTraverse()函数
            CreateBiTree1(BT);
            pushCount = popCount = 0;
            cout<<"Inorder:"; InorderTraverse(BT); cout<<endl;
            cout<<"pushCount:"<<pushCount<<endl;
            cout<<"popCount:"<<popCount<<endl;
    }
    return 0;
}
/* 请在这里填写答案 */

输入的第一行为测试模式mode赋值:

当输入的mode为0时,测试堆栈的三个函数InitStack、
GetTop、stackEmpty是否正确;
当输入的mode为1时,接着第二行输入二叉树先序的字符顺序,#表示空树,测试先序顺序建立二叉树的函数CreateBiTree是否正确,由裁判程序对二叉树进行后序遍历来测试。
当输入的mode为2时,接着第二行输入二叉树先序的字符顺序,#表示空树,测试先序遍历的非递归函数,因为非递归算法需要使用栈,因此裁判程序中会输出栈的push和pop次数;
当输入的mode为3时,接着第二行输入二叉树先序的字符顺序,#表示空树,测试中序遍历的非递归函数,因为非递归算法需要使用栈,因此裁判程序中会输出栈的push和pop次数。
输入样例:
在这里给出一组输入:

1
ABC##DE#G##F###

输出样例:
在这里给出相应的输出:

Postorder:CGEFDBA

我的答案如下:


Status InitStack(SqStack &S) {
    S.base = new SElemType[MAXSIZE];
    if (!S.base)
        return (OVERFLOW);
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return OK;
}

SElemType GetTop(SqStack S) {
    return *(S.top - 1);
}

bool stackEmpty(SqStack S) {
    if (S.top == S.base)
        return false;
    return true;
}
void CreateBiTree(BiTree &BT) {
    char ch;
    cin >> ch;
    if (ch != '#')
    {
        BT = new BiTNode;
        BT->Data = ch;
        CreateBiTree(BT->lchild);
        CreateBiTree(BT->lchild);
    }
}

void InorderTraverse( BiTree BT ) {
    //CreateBiTree(BT);
    SqStack S;
    InitStack(S);
    BiTree p = BT;
    //BiTree q = new BiTNode;
    while (p || !stackEmpty(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            cout << p->Data;
            p = p->rchild;
        }
    }
}

void PreorderTraverse( BiTree BT ) {
    //CreateBiTree(BT);
    SqStack S;
    InitStack(S);
    BiTree p = BT;
    //BiTree q = new BiTNode;
    while (p || !stackEmpty(S)) {
        if (p) {
            cout << p->Data;
            Push(S, p);
            p = p->lchild;
        } else {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

img

请问为什么错了啊?

  • 写回答

6条回答 默认 最新

查看更多回答(5条)

报告相同问题?

问题事件

  • 系统已结题 5月21日
  • 已采纳回答 5月13日
  • 创建了问题 5月12日

悬赏问题

  • ¥15 miniconda安装不了
  • ¥20 python代码编写
  • ¥20 使用MPI广播数据遇到阻塞
  • ¥15 TinyMCE如何去掉自动弹出的“链接…”工具?
  • ¥15 微信支付转账凭证,如何解决
  • ¥15 在win10下使用指纹登录时,界面上的文字最后一个字产生换行现象
  • ¥20 使用AT89C51微控制器和MAX7219驱动器来实现0到99秒的秒表计数,有开始和暂停以及复位功能,下面有仿真图,请根据仿真图来设计c语言程序
  • ¥15 51单片机 双路ad同步采样
  • ¥15 使用xdocreport 生成word
  • ¥15 请教怎么用MATLAB求坐标