创建二叉树和实现二叉树的三种遍历 a. 根据提示输入字符型数据创建二叉树,输入值为所有字符型数据 b. 输出为遍历后的每个结点的值的顺序 c. 创建二叉树并能实现二叉树的先序、中序、后序遍历
时间: 2023-10-24 13:08:37 浏览: 93
好的,下面是 Python 代码实现:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 创建二叉树
def create_tree():
val = input("请输入结点值,输入#表示空结点:")
if val == '#':
return None
node = TreeNode(val)
node.left = create_tree()
node.right = create_tree()
return node
# 先序遍历
def preorder_traverse(node):
if node:
print(node.val, end=' ')
preorder_traverse(node.left)
preorder_traverse(node.right)
# 中序遍历
def inorder_traverse(node):
if node:
inorder_traverse(node.left)
print(node.val, end=' ')
inorder_traverse(node.right)
# 后序遍历
def postorder_traverse(node):
if node:
postorder_traverse(node.left)
postorder_traverse(node.right)
print(node.val, end=' ')
# 测试
root = create_tree()
print("先序遍历:", end='')
preorder_traverse(root)
print("\n中序遍历:", end='')
inorder_traverse(root)
print("\n后序遍历:", end='')
postorder_traverse(root)
```
输入提示为:每次输入一个结点的值,如果该结点是空结点则输入#。例如,若要创建如下二叉树:
```
A
/ \
B C
/ \
D E
```
则应按以下顺序输入值:A、B、#、#、C、D、#、#、E、#、#。
输出为先序、中序、后序遍历的结果。
阅读全文