|
7-23 建立与遍历二叉树 (70 分)
以字符串的形式定义一棵二叉树的先序序列，若字符是‘#’, 表示该二叉树是空树，否则该字符是相应结点的数据元素。读入相应先序序列，建立二叉链式存储结构的二叉树，然后中序遍历该二叉树并输出结点数据。
输入格式:
字符串形式的先序序列（即结点的数据类型为单个字符）
输出格式:
中序遍历结果
输入样例:
在这里给出一组输入。例如：
ABC##DE#G##F###
输出样例:
在这里给出相应的输出。例如：
CBEGDFA
代码如下：?
#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct TNode* Position;
typedef Position BinTree;
typedef struct TNode {
ElementType data;
BinTree lchild;//左指针
BinTree rchild;//右指针
};
BinTree CreateBiTree(BinTree T);//构造二叉链表表示的二叉树T
void InOrder(BinTree T);//中序遍历
void visit(BinTree T);//访问根结点
int main() {
BinTree BT = (BinTree)malloc(sizeof(struct TNode));
BT = CreateBiTree(BT);
InOrder(BT);
printf("\n");
return 0;
}
BinTree CreateBiTree(BinTree T) {
//按先序次序输入二叉树中结点的值（一个字符），#字符表示空树
T=(BinTree)malloc(sizeof(struct TNode));
char ch;
ch=getchar();
if (ch == '#') T = NULL;
else {
T->data = ch;
T->lchild = CreateBiTree(T->lchild);
T->rchild = CreateBiTree(T->rchild);
}
return T;
}
void visit(BinTree T) {
printf("%c", T->data);
}
void InOrder(BinTree T) {
if (T != NULL) {
InOrder(T->lchild);//递归遍历左子树
visit(T);//访问根结点
InOrder(T->rchild);//递归遍历右子树
}
}
?
|