牛客网 TSINGK110 二叉树遍历算法与实现

牛客网 TSINGK110 二叉树遍历算法与实现1.题目描述描述编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。输入描述输入包括1行字符串长度不超过100。输出描述可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。输入abc##de#g##f###输出c b e g d f a2.分析题目与解题步骤分析示例中的二叉树2.1 先创建二叉树的结构typedef struct TreeNode{ char data; //保存的字符数据 struct TreeNode *left; //左子树 struct TreeNode *right; //右子树 }TreeNode;2.2为用户输入的字符串创建二叉树TreeNode *createTree(char* arr,int *pi) { if(arr[*pi]#) //如果用户输入的字符为#先pi然后返回空 { (*pi); return NULL; } TreeNode *Node BuyNode(arr[*pi]); //为结点开辟空间 (*pi); //递归创建左子树和右子树 Node-leftcreateTree(arr,pi); Node-rightcreateTree(arr,pi); return Node; }2.2.1为结点开辟空间TreeNode *BuyNode(char ch) { TreeNode*Node(TreeNode*)malloc(sizeof(TreeNode)); if(NodeNULL) { perror(malloc fail!); exit(1); } Node-datach; Node-leftNULL; Node-rightNULL; return Node; }2.3中序遍历再打印出来void inorder(TreeNode *root) { if(rootNULL) { return; } inorder(root-left); printf(%c ,root-data); inorder(root-right); }2.4主函数的代码实现int main() { char arr[100]; scanf(%s,arr); int i0; TreeNode *rootcreateTree(arr,i); inorder(root); return 0; }如有不足或错误欢迎各位指出