二叉树深度周游算法（递归，非递归）

能帮我看看这个求二叉树深度周游算法的代码哪里写错了吗？编译器一直报错

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char DataType;
struct SeqBinTree{
 int maxnum;
 int n;
 DataType *nodelist;
};
typedef struct SeqBinTree *PSeqBinTree;

int leftChild_seq(PSeqBinTree t){
    return (t->nodelist[0]*2+1);
}

int rightChild_seq(PSeqBinTree t){
    return (t->nodelist[0]*2+2);
}

void visit(PSeqBinTree p){
 printf("%c",p->nodelist);
 return 0;
}

struct SeqStack{
  int maxnum;
  int b;
  DataType *s;
  };
typedef struct SeqStack *PSeqStack;

PSeqBinTree t;
PSeqBinTree creatEmptyBinTree(){
  int m;
  t=(PSeqBinTree*)malloc(sizeof(struct SeqBinTree));
  if(t==NULL){
  return 0;
  }
  t->nodelist=(DataType*)malloc(m*sizeof(DataType));
  t->maxnum=m;
  t->n=0;
  return t;
}

void PreOrder28(PSeqBinTree t){
 if(t==NULL)
 return 0;
 visit(root(t));
 PreOrder28(leftChild(t));
 PreOrder28(rightChild(t));
}

void inOrder28(PSeqBinTree t){
 if(t==NULL)
 return 0;
 inOrder28(leftChild(t));
 visit(root(t));
 inOrder28(rightChile(t));
}

void postOrder28(PSeqBinTree t){
 if(t==NULL)
 return 0;
 postOrder28(leftChild(t));
 postOrder28(rightChild(t));
 visit(root(t));
}

PSeqStack pastack;
PSeqStack creatEmptyStack_seq(){
 pastack=(PSeqStack*)malloc(sizeof(struct SeqStack));
 pastack->b=-1;
}

int isEmptyStack(PSeqStack s){
  if(pastack->b==-1)
  return 1;
  return 0;
}

DataType top(PSeqStack s){
return pastack->b;
}

void push(PSeqStack pastack,PSeqBinTree c){
 if(pastack->b>pastack->maxnum-1)
 printf("Overflow!\n ");
 pastack->b++;
 pastack->s[pastack->b]=c;
}

void pop(PSeqStack pastack){
  if(pastack==-1)
  printf("underflow\n");
  pastack->b=pastack->b-1;
}

void nPreOrder28(PSeqBinTree t){
  PSeqStack s;
  PSeqBinTree c;
  if(t==NULL)
  return 0;
  s=creatEmptyStack();
  push(s,t);
    while(!isEmptyStack(s)){
    c=top(s);pop(s);
    if(c!=NULL){
    visit(root(c));
    push(s,rightChild(c));
    push(s,leftChild(c));
    }
  }
}

void nInOrder28(PSeqBinTree t){
 PSeqStack s=creatEmptyStack();
 PSeqBinTree c=t;
 if(c==NULL)return 0;
  do{
     while(c!=NULL){
     push(s,c);
     c=leftChild(c);
     }
    c=top(s);pop(s,c);visit(root(c));c=rightChild(c);
  }while(c!=NULL||!isEmptyStack(s));
}

void npostOrder28(PSeqBinTree t){
  PSeqStack s=creatEmptyStack();
  PSeqBinTree p=t;
  while(p!=NULL||!isEmptyStack(s)){
     while(p!=NULL){
     push(s,p);
     p=leftChild(p)?leftChild(p):rightChild(p);
     }
     p=top(s);pop(s);visit(root(p));
     if(!isEmptyStack&&leftChild(s)==p)
       p=rightChild(s);
     else p=NULL;
   }
}
int main(){
char *nodelist[];
PSeqBinTree t;
t->(*nodelist[])={A,B,C,^,D,E};
printf("递归遍历\n");
printf("\n先根");
PreOrder28(PSeqBinTree t);
printf("\n中根");
inOrder28(PSeqBinTree t);
printf("\n后根");
postOrder28(PSeqBinTree t);
printf("\n非递归遍历");
printf("\n先根");
nPreOrder28(PSeqBinTree t);
printf("\n中根");
nInOrder28(PSeqBinTree t);
printf("\n后根");
npostOrder28(PSeqBinTree t);
return 0;
}

可能存在以下问题
1、在 PSeqBinTree 的结构体定义中没有定义 root、leftChild、rightChild，因此需要加上：

struct SeqBinTree {
    int maxnum;
    int n;
    DataType *nodelist;
};

typedef struct SeqBinTree *PSeqBinTree;

#define root(t) t->nodelist[0]
#define leftChild(t,i) t->nodelist[i*2+1]
#define rightChild(t,i) t->nodelist[i*2+2]

2、在 creatEmptyBinTree 函数中定义了 int m 但没有初始化为任何值，因此在 malloc 中分配内存时会出现随机值，需要给 m 赋初值。
3、在 visit 函数中，应该输出树节点的数据，而不是输出整个节点数组，应该改为这样：

void visit(PSeqBinTree p){
    printf("%c",p->nodelist[p->n]);
}

4、在 main 函数中，定义字符数组应使用 [] 而不是 *，同时，数组的元素应该用单引号括起来表示字符，可以这样修改：

char nodelist[]={'A','B','C','^','D','E'};

5、在 main 函数中，给 t->(*nodelist[]) 赋初值的写法不正确，正确的方法是遍历 nodelist 数组，将其中的每一个元素插入到二叉树中：

for (int i = 0; i < sizeof(nodelist); i++) {
    t->nodelist[i] = nodelist[i];
    t->n++;
}

6、PreOrder28、inOrder28、postOrder28 函数中，需要使用 root、leftChild、rightChild 宏定义来访问二叉树中的节点，应该改为这样：

void PreOrder28(PSeqBinTree t){
    if(t==NULL)
        return;
    visit(root(t));
    PreOrder28(leftChild(t, 0));
    PreOrder28(rightChild(t, 0));
}

void inOrder28(PSeqBinTree t){
    if(t==NULL)
        return;
    inOrder28(leftChild(t, 0));
    visit(root(t));
    inOrder28(rightChild(t, 0));
}

void postOrder28(PSeqBinTree t){
    if(t==NULL)
        return;
    postOrder28(leftChild(t, 0));
    postOrder28(rightChild(t, 0));
    visit(root(t));
}

7、creatEmptyStack_seq 函数中返回的是 PSeqStack 类型的指针，而不是 void，应该改为这样：

PSeqStack creatEmptyStack_seq(){
    PSeqStack s = (PSeqStack) malloc(sizeof(struct SeqStack));
    s->b=-1;
    return s;
}

8、push 函数中将元素加入到栈顶时应该使用下标操作符 []，而不是函数调用符 ()，应该改为这样：

void push(PSeqStack s, PSeqBinTree c){
    if(s->b>s->maxnum-1)
        printf("Overflow!\n");
    s->b++;
    s->s[s->b]=c;
}

9、pop 函数中，应该判断栈是否为空，并且弹出栈顶元素时应该使用下标操作符 []，应该改为这样：

void pop(PSeqStack s){
    if(s->b==-1)
        printf("underflow\n");
    else
        s->b--;
}

10、nInOrder28 函数中判断栈是否为空时调用了错误的函数名，应该改为这样：

while(c!=NULL||!isEmptyStack(s)){
    while(c!=NULL){
        push(s,c);
        c=leftChild(c)?leftChild(c):rightChild(c);
    }
    c=top(s);pop(s);visit(root(c));
    if(!isEmptyStack(s)&&leftChild(s,top(s))==p)
        p=rightChild(s,top(s));
    else p=NULL;
}

可以参考下

// DS05_01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include"BinaryTree.cpp"
#include"BinaryTreeNode.h"
#include <iostream>
using namespace std;
int main()
{
    BinaryTree<char> a, b, c, d, e, f, g, h, i, j, k, nullTree;
    k.CreateTree('K', nullTree, nullTree);
    j.CreateTree('J', nullTree, k);
    i.CreateTree('I', nullTree, nullTree);
    h.CreateTree('H', nullTree, nullTree);
    g.CreateTree('G', j, nullTree);
    f.CreateTree('F', nullTree, i);
    e.CreateTree('E', h, nullTree);
    d.CreateTree('D', nullTree, nullTree);
    c.CreateTree('C', f, g);
    b.CreateTree('B', d, e);
    a.CreateTree('A', b, c);
    cout << "深度优先周游二叉树如下：" << endl;
    cout << "前序周游二叉树：" << endl;
    a.PreOrder(a.getRoot());
    cout << endl;
    cout << "中序周游二叉树：" << endl;
    a.InOrder(a.getRoot());
    cout << endl;
    cout << "后序周游二叉树：" << endl;
    a.PostOrder(a.getRoot());
    cout << endl;
    cout << endl;
    cout << "广度优先周游二叉树：" << endl;
    a.LevelOrder(a.getRoot());
    return 0;
}
 
//*******一场过云雨*******
 

• 你可以看下这个问题的回答https://ask.csdn.net/questions/219020
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：根据中序遍历和后序遍历求二叉树的先序遍历
• 除此之外, 这篇博客: 研究树为什么要重点研究二叉树？一次性搞懂二叉树和树的初阶知识中的 🍜1.前序遍历算法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• void PreOrderTraverse(BiTree T)
  {
  	if (T == NULL)
  	{
  		return;
  	}
  	printf("%d ", T->data);
  	PreOrderTraverse(T->leftchild);
  	PreOrderTraverse(T->rightchild);
  }
  

• 您还可以看一下 张传波老师的软件设计是怎样炼成的？课程中的 架构设计的第二层拆解小节, 巩固相关知识点
  
• 以下回答由chatgpt基于相关博客总结生成:

  我需要您提供二叉树深度周游算法的代码以便我检查可能出现的编译错误。请提供代码或错误提示。

以下答案由GPT-4.5Plus大模型(语音)与博主A努力中.......共同编写：
我看了你的代码,发现有几个问题:

1. t的定义方式不正确。t应定义为:

c
struct SeqBinTree *t;
而不是:
c
PSeqBinTree t;
PSeqBinTree是结构体指针类型,不能直接定义变量。

2. creatEmptyBinTree的参数m没有使用。应删除该参数。
3. nodelist应定义为:

c
DataType nodelist[];
 
而不是: 
c 
DataType *nodelist[];
后者是指针数组,而非字符数组。

4. 递归遍历函数PreOrder28、inOrder28和postOrder28的参数应为结构体指针t,而非t本身:

c
void PreOrder28(struct SeqBinTree *t)
{
    // ...
}

5. 非递归遍历函数的参数同样应为结构体指针,并且在函数体内应将结构体指针c赋值给p,而非直接使用c:

c
void nPreOrder28(struct SeqBinTree *t) 
{
    struct SeqBinTree *p = t;
    // ...
    p = c; 
}

6. main函数中,t的初始化应为:

c
struct SeqBinTree *t = creatEmptyBinTree();
t->nodelist = {'A', 'B', 'C', '^', 'D', 'E'};

修正以上问题后,你的代码应该可以编译成功。具体修正后的代码如下:

c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char DataType;
struct SeqBinTree{
 int maxnum;  
 int n;  
 DataType nodelist[];
};
typedef struct SeqBinTree *PSeqBinTree;  

// ...

struct SeqBinTree *t;
PSeqBinTree creatEmptyBinTree(){
  int m;
  t=(struct SeqBinTree*)malloc(sizeof(struct SeqBinTree));
  t->nodelist=(DataType*)malloc(sizeof(DataType)*6); 
  t->maxnum=6;
  t->n=6;
  return t;
}  

void PreOrder28(struct SeqBinTree *t){  
    // ...
}

void nPreOrder28(struct SeqBinTree *t)  {  
    struct SeqBinTree *p = t; 
    // ...
    p = c;  
}

int main(){
struct SeqBinTree *t = creatEmptyBinTree();
t->nodelist = {'A', 'B', 'C', '^', 'D', 'E'};  
// ...
}

希望这个分析能帮助你解决二叉树遍历算法的编译错误。

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
这段代码中存在以下问题：

1. 在声明SeqBinTree和SeqStack时，应该使用结构体，而非指向结构体的指针。

应该修改为：

typedef struct SeqBinTree{
   int maxnum;
   int n;
   DataType *nodelist;
} SeqBinTree;

typedef struct SeqStack{
   int maxnum;
   int b;
   DataType *s;
} SeqStack;

2. 在 creatEmptyBinTree 函数中，m 未定义，导致分配内存失败。

需要在函数中添加 m 的定义及赋值：

PSeqBinTree creatEmptyBinTree(){
   int m = 10;
   t=(PSeqBinTree)malloc(sizeof(SeqBinTree));
   if(t==NULL){
      return NULL;
   }
   t->nodelist=(DataType*)malloc(m*sizeof(DataType));
   t->maxnum=m;
   t->n=0;
   return t;
}

3. 在定义 nodelist 的地方，需要将每个节点的字符用单引号括起来，否则编译器会报错：

char *nodelist[] = {'A', 'B', 'C', '^', 'D', 'E'};

4. 在访问节点时，应该访问节点的值，而非节点本身。visit 函数参数应该传入节点的值。

void visit(DataType val){
   printf("%c", val);
}

5. 在定义 creatEmptyStack_seq 函数时，没有给 SeqStack 分配内存。

需要在函数中添加分配内存的代码：

PSeqStack creatEmptyStack_seq(){
   pastack=(PSeqStack)malloc(sizeof(SeqStack));
   pastack->b=-1;
   pastack->s = (DataType*)malloc(sizeof(DataType) * 10);
   return pastack;
}

6. 调用 creatEmptyStack 函数时存在语法错误，应该为 creatEmptyStack_seq。

PSeqStack s;
PSeqBinTree c;
if(t==NULL)
   return 0;
s=creatEmptyStack_seq();

7.在 nPreOrder28 函数、nInOrder28 函数、npostOrder28 函数中，顺序栈的判空应该使用参数 s（即传入的顺序栈），而非全局变量 pastack。

int isEmptyStack(PSeqStack s){
   if(s->b==-1)
      return 1;
   return 0;
}

void pop(PSeqStack s){
   if(isEmptyStack(s))
      printf("underflow\n");
   s->b=s->b-1;
}

修改后的完整代码如下：
如果我的回答解决了您的问题，请采纳！