输入

输入的第一行包含单独的一个数字T，表示测试序列的数目；

以下每一行为一个测试序列,测试序列是按先序序列输入字符,如果节点没有左或右孩子,则输入用空格表示,最后用一个空格结束一行的输入。

输出

对应每个测试序列，采用中序遍历二叉线索树，输出一行

输入样例 1  点击复制

2
ABD##E##CG##F##  
*+a##b##-c##d##

输出样例 1

DBEAGCF
a+b*c-d

#include <stdio.h>
#include <stdlib.h>
#define elemtype char
typedef struct node { //线索二叉树elemtype data;struct node*lchild, *rchild; //左右孩子指针int ltag, rtag; //左右线索标志
} *threadtree, threadnode;void visit(threadnode*T){//输出一个节点printf("%c",T->data);}
int u=0;
char chh[500];
void CreateThreadTree(threadnode** T) {char ch = chh[u++];if (ch == '#') {*T = NULL;return;} else {*T = (threadtree)malloc(sizeof(threadnode));(*T)->ltag = (*T)->rtag = 0; // 存在左右孩子(*T)->data = ch;CreateThreadTree(&((*T)->lchild));CreateThreadTree(&((*T)->rchild));return;}
}
void InOrder(threadnode*T) {//中序遍历线索二叉树if (T) {if (T->ltag != 1)InOrder(T->lchild);visit(T);if(T->rtag != 1)InOrder(T->rchild);}
}int main() {int t;scanf("%d",&t);getchar();while(t--){u=0;scanf("%s",chh);threadtree T=(threadtree)malloc(sizeof(threadnode));CreateThreadTree(&T);InOrder(T);printf("\n");}
}