机试小课堂丨数据结构周·例题讲解①《二叉树遍历》

【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】

苏世机试小课堂，考研机试不再慌！

公主号：苏世学社考研　　苏世计算机考研

二叉树遍历

题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串：ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

示例

输入

输入包括1行字符串，长度不超过100。

输出

可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。

样例输入

   abc##de#g##f###

样例输出

   c b e g d f a

    

答案

①读题:

本题题意很明显，根据给出的先序遍历找出中序遍历。

②想出思路：

创建一个字符数组存放接收的字符，调用创建函数，先序创建一个二叉树，然后调用中序遍历函数输出。

③动手编程：

④测试样例：

⑤提交代码：

进入下面的链接提交核心代码：

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=40&&tqId=21342&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回测评结果：

本题总结

本题是一道由先（前）序遍历转换为中序遍历的问题，创建一个字符数组用来存字符，做一个结构体表示一个树结点，调用CreateTree()函数来递归建树，建好之后递归中序输出即可。注意建树的时候传的参数是地址。

未完待续

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导