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

二叉树非递归遍历算法

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

栈的初始化函数、取栈顶元素,栈是否为空,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月21日
      • 已采纳回答 5月13日
      • 创建了问题 5月12日

      悬赏问题

      • ¥50 R语言时间序列 滚动窗口预测
      • ¥15 Python不使用Selenium怎么实现网页输入和点击
      • ¥50 vue百度地图导致浏览器崩溃
      • ¥15 请问这段C语言代码应该如何修改呢
      • ¥20 Latex 转入带数式的曲线图后数式部分报错
      • ¥15 Arcgis基于一幅栅格提取另一幅栅格单元值
      • ¥15 Verilog数据产生器代码疑点
      • ¥15 电脑部分网页无法访问是为什么?
      • ¥15 如何在vscode导出pdf失败了,拓展也安装了?
      • ¥15 使用python-kivy如何点击按钮选择手机相册中的图片?