6-1 二叉树的遍历 分数 30 作者 YJ 单位 西南石油大学 输入二叉树的先序遍历序列，以#代表空树，输出该二叉树的中序遍历序列。例如，有如下二叉树，其先序序列为：ABC##DE#G##F###，输出其中序序列：CBEGDFA 二叉树1.jpg 二叉树采用二叉链表存储结构，其定义为： typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; 函数接口定义： void InOrder(BiTree Tree)//中序遍历 void creat(BiTree &Tree)//构建二叉树 其中， Tree 是用户传入的参数，为指向二叉树根节点的指针。 裁判测试程序样例： #include<stdio.h> #include<malloc.h> #define len sizeof(struct BiTNode ) typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; void InOrder(BiTree Tree)； void creat(BiTree &Tree); int main() { BiTree Tree; creat(Tree);//创建二叉树 InOrder(Tree);//中序遍历 return 0; } /* 请在这里填写答案 */ 输入样例： ABC##DE#G##F### 输出样例： CBEGDFA

下面是题目的完整代码实现：

#include<stdio.h>
#include<malloc.h>
#define len sizeof(struct BiTNode )

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

void InOrder(BiTree Tree);//中序遍历
void creat(BiTree &Tree);//构建二叉树

int main() {
    BiTree Tree;
    creat(Tree);//创建二叉树
    InOrder(Tree);//中序遍历
    return 0;
}

void creat(BiTree &Tree) {
    char ch;
    scanf("%c",&ch);
    if(ch == '#') {
        Tree = NULL;
    } else {
        Tree = (BiTNode*)malloc(len);
        Tree->data = ch;
        creat(Tree->lchild);
        creat(Tree->rchild);
    }
}

void InOrder(BiTree Tree) {
    if(Tree) {
        InOrder(Tree->lchild);
        printf("%c",Tree->data);
        InOrder(Tree->rchild);
    }
}

这里使用了递归的方式，先读入一个字符，如果是 '#' 则表示该节点为空，否则就分配空间并设置节点值，然后递归构建左右子树。中序遍历同理，先遍历左子树，然后输出节点值，最后遍历右子树。