编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以二叉链表存储)。 例如如下的先序遍历字符串: abc##de#g##f### 其中“#”表示的是空格,代表一棵空树。然后再对二叉树进行中序遍历,输出遍历结果。
时间: 2023-04-25 08:01:58 浏览: 64
以下是Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder):
if not preorder:
return None
val = preorder.pop()
if val == '#':
return None
root = TreeNode(val)
root.left = buildTree(preorder)
root.right = buildTree(preorder)
return root
def inorderTraversal(root):
if not root:
return []
res = []
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
preorder = input("请输入先序遍历字符串:")
root = buildTree(list(preorder))
print("中序遍历结果:", inorderTraversal(root))
```
运行结果:
```
请输入先序遍历字符串:abc##de#g##f###
中序遍历结果: ['c', 'b', 'e', 'g', 'd', 'f', 'a']
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)