- 总时间限制: 1000ms 内存限制:65535kB
- 描述
-
给出一颗二叉树根节点到各叶子节点的路径，建立这颗二叉树，输出中序遍历的结果。
- 输入
- 第一行输入一个整数t，代表测试数据的组数。
对于每组测试数据，第一行输入一个整数n，代表二叉树根节点到各叶子节点的路径数目。
随后输入n行，每行包含一个字符串S, 代表从根节点走向对应叶子节点的路径。
路径中每个节点用两个字符表达：第一个字符要么为 ‘+’ 要么为 ‘-‘， ‘+’代表网左孩子方向走，’-’代表往右孩子方向走。第二个字符是一个大写的英文字母，表示对应节点编号。
比如 +B-C 代表 从根结点向左走到B节点，再向右走到C节点。
根节点编号始终是字符‘A’，不会有重复编号的节点。
字符串S长度不超过20 , n <= 26 - 输出
- 每组测试数据，输出一行，对应二叉树的中序遍历结果。
- 样例输入
-
3
3
+B-D
-C+E
-C-F
2
+B
-C
1
+B+C+D+E
- 样例输出
-
BDAECF
BAC
EDCBA
- 提示
- 二叉树的节点用结构体存储。
结构体声明为：
struct Node
{
char c;
struct Node *ls , *rs;
};
创建一个新节点通过malloc函数实现
Node *node = (Node *)malloc(sizeof(Node));
如果对于指针使用不熟悉，也可以采用数组下标来实现。
结构体声明成以下形式：
struct Node
{
char c;
int ls , rs;
};
同时开辟一个数组
struct Node node[110];
用一个变量p来控制每次新节点的申请。
#include <stdio.h> #include <malloc.h> #define MAXSIZE 100 char str[MAXSIZE]; typedef struct node { char data; struct node *lchild; struct node *rchild; }Btree; Btree *b; void creatree(char *str) { char *ch=str; Btree *t=b,*s; while(*ch!='\0') { switch(*ch) { case '+':ch++; s=(Btree *)malloc(sizeof(Btree)); s->lchild=NULL; s->rchild=NULL; s->data=*ch; if(t->lchild==NULL) t->lchild=s; t=t->lchild; break; case '-':ch++; s=(Btree *)malloc(sizeof(Btree)); s->lchild=NULL; s->rchild=NULL; s->data=*ch; if(t->rchild==NULL) t->rchild=s; t=t->rchild; break; } ch++; } } void inorder (Btree *root) { if(root!=NULL) { inorder (root->lchild); printf("%c",root->data); inorder(root->rchild); } } int main() { int t,n; scanf("%d",&t); while(t--) { b=(Btree *)malloc(sizeof(Btree)); b->lchild=NULL; b->rchild=NULL; b->data='A'; scanf("%d",&n); getchar(); while(n--) { gets(str); creatree(str); } inorder(b); printf("\n"); } return 0; }