请问这个问题如何处理

Question

问题遇到的现象和发生背景
以二叉链表作存储结构，建立一棵二叉树， 输出该二叉树的先序，中序，后序遍历序列。

二叉链表的类型描述：

typedef char ElemType;
typedef struct BiNode
{ ElemType data;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
输入格式:
输入一个二叉树的先序序列，空的位置以#替代。

输出格式:
输出该二叉树的先序遍历序列。输出的遍历序列中字符间均无间隔。

Answer 1

一、实验目的

1. 通过练习进一步认识非线性结构的特征；
2. 掌握树状结构与线性结构的差别；
3. 掌握树的存储结构及遍历二叉树的方法。

二、实验内容
①题目：
先序建立并以递归与非递归方式前中后序遍历二叉树。
建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序，中序和后序），打印遍历输出结果。
【基本要求】从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序，中序，后序），然后将遍历结果打印输出。要求采用递归与非递归方式实现。
【测试数据】 ABC##DE#G##F###
【输出结果】
先序序列为 ABCDEGF
中序序列为 CBEGDFA
后序序列为 CGEFDBA
②实验过程：
1.程序设计思路：
A.递归方法
前序根 左 右；中序左 根 右；后序左 右 根。
B.非递归遍历思想:
非递归前序遍历二叉树:
若栈不为空且p不为空时入栈即出栈并打印,然后将其右孩子入栈,再继续访问其左孩子;若p为空,则出栈。
非递归中序遍历二叉树:
从根结点开始,让二叉树左中右遍历,若不为空则入栈,若为空则出栈。
非递归后序遍历二叉树:
每个结点都要进栈俩次,第二次退栈时才访问结点。第一次进栈时，在遍历左子树的过程中将根结点进栈，待左子树访问完后，回溯的结点退栈，即退出这个根结点，但不能立即访问，只能借助这个根去找该根的右子树，并遍历这棵右子树，直到该右子树全部遍历以后，再退出该根结点，并访问它。所以，为了记录结点是第一次还是第二次进栈，需单独定义一个结点作为标志。
2.程序源代码：
方法一：递归方式遍历

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct Node
{
    char data;
    struct Node* LChild;
    struct Node* RChild;

}BiTNode, * BiTree;

void PreOrder(BiTree root);
void InOrder(BiTree root);
void PostOrder(BiTree root);

void Visit(char x) {
    putchar(x);
}
BiTree CreateBiTree(BiTree T)
{
    char ch;
    ch = getchar();
    if (ch == '#')
        return NULL;
    else
    {
        T = (BiTree*)malloc(sizeof(BiTNode));
        T->data = ch;
        T->LChild = CreateBiTree(T->LChild);
        T->RChild = CreateBiTree(T->RChild);
    }
    return T;
}
//递归方式前序遍历二叉树
void PreOrder(BiTree root)
{
    if (root != NULL) {
        Visit(root->data);
        PreOrder(root->LChild);
        PreOrder(root->RChild);
    }

}
//递归方式中序遍历二叉树
void InOrder(BiTree root)
{
    if (root != NULL) {
        InOrder(root->LChild);
        Visit(root->data);
        InOrder(root->RChild);
    }

}
//递归方式后序遍历二叉树
void PostOrder(BiTree root)
{
    if (root != NULL) {
        PostOrder(root->LChild);
        PostOrder(root->RChild);
        Visit(root->data);
    }
}
int main()
{
    BiTree T=NULL;
    printf("请依次输入二叉树的结点：\n");
    T = CreateBiTree(T);
    printf("先序遍历结果为: \n");
    PreOrder(T);
    printf("\n中序遍历结果为: \n");
    InOrder(T);
    printf("\n后序遍历结果为: \n");
    PostOrder(T);
    return 0;
}

运行截图

**
方法二:用栈消除递归遍历二叉树(前,中,后序)**

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define Stack_Size 100//设栈中元素个数为100个
//定义结构体二叉树
typedef struct Node
{
    char data;
    struct Node* LChild;
    struct Node* RChild;
}BiTNode, * BiTree;

//定义结构体顺序栈
typedef BiTree StackElementType;
typedef struct {
    StackElementType elem[Stack_Size];//存放栈中元素的一维数组
    int top;//栈顶元素下标,top为-1表示空栈
}SeqStack;
SeqStack S;//定义一个全局栈
BiTree p;//定义一各全局树指针
void Visit(char x) {
    putchar(x);
}
//先序遍历创建二叉树
BiTree CreateBiTree(BiTree T)
{
    char ch;
    ch = getchar();
    if (ch == '#')
        return NULL;
    else
    {
        T = (BiTree*)malloc(sizeof(BiTNode));
        T->data = ch;
        T->LChild = CreateBiTree(T->LChild);
        T->RChild = CreateBiTree(T->RChild);
    }
    return T;
}


//初始化空栈
void InitStack(SeqStack *S) 
{
    S -> top = -1;
}
//压栈
int Push(SeqStack *S, StackElementType x)
{
    if (S->top == Stack_Size - 1) return FALSE;//
    S->top++;
    S->elem[S->top] = x;
    return TRUE;
}
//出栈
int Pop(SeqStack *S, StackElementType *x)
{
    if (S->top == -1)
        return FALSE;
    else
    {
        *x = S->elem[S->top];
        S->top--;
        return TRUE;
    }
}
//判断栈是否为空
int IsEmpty(SeqStack *S)
{
    if (S->top==-1) return TRUE;//空栈返回1
    else
        return FALSE;//非空栈返回0
}
//非递归前序遍历二叉树
/*若栈不为空且p不为空时入栈即出栈并打印,然后将其右孩子入栈,
再继续访问其左孩子;若p为空,则出栈*/
void PreOrderByStack(BiTree root) 
{
    InitStack(&S);
    p = root;
    if (p == NULL) return;
    while (p !=NULL||!IsEmpty(&S))
    {
        if (p)
        {
            Push(&S, p);
            Pop(&S, &p);
            Visit(p->data);
            Push(&S, p->RChild);
            p = p->LChild;
        }
        else 
            Pop(&S, &p);
    }
}


//非递归中序遍历二叉树
/*从根结点开始,让二叉树左中右遍历,若不为空则入栈,若为空出栈*/
void InOrderByStack(BiTree root)
{    
     InitStack(&S);
     p = root;
     if (p == NULL) return;
    while (p!=NULL||!IsEmpty(&S))
    {    
        if (p != NULL)//根指针进栈,遍历左子树
        {
            Push(&S, p);
            p = p->LChild;
        }
        else
        {//根指针退栈,访问根结点,遍历右子树
            Pop(&S, &p);
            Visit(p->data);    
            p = p->RChild;
        }
    }
}
//非递归后序遍历二叉树
/*每个结点都要进栈俩次,第二次退栈时才访问结点。第一次进栈时，
在遍历左子树的过程中将根结点进栈，待左子树访问完后，回溯的结点退栈，
即退出这个根结点，但不能立即访问，只能借助这个根去找该根的右子树，
并遍历这棵右子树，直到该右子树全部遍历以后，再退出该根结点，并访问它。
所以，为了记录结点是第一次还是第二次进栈，需单独定义一个结点作为标志。*/
void PostOrderByStack(BiTree root)
{
    InitStack(&S);
    p = root;
    if (p == NULL) return;
    BiTree* tag = NULL;//定义的标志
    while (p != NULL || !IsEmpty(&S))
    {
        while (p!=NULL)
        {
            Push(&S, p);
            p = p->LChild;
        }
        Pop(&S,&p);//遇到空直接出栈
        if (p->RChild==NULL||p->RChild==tag)
        {
            Visit(p->data);
            tag = p;
            p = NULL;
        }
        else
        {
            Push(&S, p);
            p = p->RChild;
        }
    }
}
int main()
{    
    BiTree T=NULL;

    printf("请依次输入二叉树的结点：\n");
    T = CreateBiTree(T);
    printf("\n先序非递归遍历结果为: \n");
    PreOrderByStack(T);
    printf("\n中序非递归遍历结果为: \n");
    InOrderByStack(T);
    printf("\n后序非递归遍历结果为: \n");
    PostOrderByStack(T);

    return 0;
}

运行截图

有用请点采纳 ，谢谢！