二叉树的中序遍历算法，这棵树有什么问题？为什么会输出来一个问号？

先序递归遍历输出时没有任何问题
中序非递归遍历时只输出了一个“？”


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSSIZE 100 //栈的最大空间

typedef struct BiNode
{
    char data;
    struct BiNode* Lchild, * Rchild;
}BiNode,*BiTree;

typedef struct
{
    BiTree top;
    BiTree base;
}SqStack;

void Initial_Stack(SqStack &s)
{
    s.base = (BiTree)malloc(MAXSSIZE * sizeof(BiNode));
    if (!s.base) printf("%s\n", strerror(errno));
    else
    {
        s.top = s.base;
        printf("Stack initialized\n");
    }

}

int Stackempty(SqStack s)
{
    if (s.top == s.base) return 1;
    else return 0;
}

int Push(SqStack& s, BiNode tmp)
{
    if (s.top - s.base >= MAXSSIZE) printf("Stack full\n");
    else
    {
        *s.top = tmp;
        s.top++;
        return 1;
        //printf("Elem pushed\n");
    }
}

void Pop(SqStack& s, BiNode& q)
{
    if (s.base == s.top) printf("Stack empty\n");
    else
    {
        q = *s.top;
        s.top--;
        //printf("Elem poped\n");
    }
}

int InOrderTraverse(BiTree T)//中序遍历非递归算法
{
    SqStack s;
    Initial_Stack(s);
    BiTree tmp=T;
    BiNode q;
    while(tmp || !Stackempty(s))
    {
        if (tmp)
        {
            Push(s, *tmp);
            tmp = tmp->Lchild;
        }
        else
        {            
            Pop(s, q);
            printf("%c ", q.data);
            tmp = q.Rchild;
        }

    }
    return 1;
}

void CreateBiTree(BiTree& T)
{
    char weight;
    //printf("Please input the weight\n");
    scanf("%c", &weight);
    if (weight == '#') T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiNode));
        T->data = weight;
        //printf("OK\n");
        CreateBiTree(T->Lchild);
        CreateBiTree(T->Rchild);
    }
}
int main()
{
    
    BiTree T;
    CreateBiTree(T);//先序创建二叉树
    InOrderTraverse(T);//中序遍历非递归算法
    return 0;
}

问题在 void Pop(SqStack& s, BiNode& q) 出栈函数第 54 55行两行代码，将两行位置互换即可：

void Pop(SqStack& s, BiNode& q)
{
    if (s.base == s.top)
        printf("Stack empty\n");
    else
    {
        s.top--;    // s.top--; 在前    修改
        q = *s.top; // 出栈在后         修改
        //printf("Elem poped\n");
    }
}

gpt
在给定的代码中，问题出现在 CreateBiTree 函数。它使用先序遍历的二叉树，但在输入节点数据时使用了 scanf，这会导致输入缓冲区残留一个换行符（'\n'）。

问题导致的现象是，在执行中序遍历时，程序会立即读取到这个换行符，并将其误认为是一个字符节点进行输出，因此输出了问号（'?'）。

要解决这个问题，可以在 CreateBiTree 函数的输入前使用 getchar() 来清空输入缓冲区的换行符，使得下一个字符能够正确输入。

修改后的代码如下所示：

void CreateBiTree(BiTree& T)
{
    char weight;
    getchar(); // 清空输入缓冲区的换行符
    scanf("%", &weight);
    if (weight == '#') T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiNode));
        T->data = weight;
        CreateBiTree(T->Lchild);
        CreateBiTree(T->Rchild);
    }
}

这样，输入的字符节点就可以正确地构建二叉树，并且中序遍历不再输出问号。

从代码中看不出有输出问号的问题，可能是输入时出现了特殊字符导致输出异常。建议检查输入的二叉树数据是否正确，是否符合中序遍历的规则。另外，可以考虑在输出每个节点数据时，添加一些调试信息，以便更好地定位问题。例如，可以在输出节点数据时，同时输出节点的地址，以便确认是否正确访问了每个节点。