数据结构实验二叉树的创建和实现三种遍历
时间: 2023-11-05 13:04:17 浏览: 63
好的,以下是创建二叉树和实现三种遍历的代码:
```python
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def create_tree(arr, root, i, n):
if i < n:
temp = Node(arr[i])
root = temp
root.left = create_tree(arr, root.left, 2 * i + 1, n)
root.right = create_tree(arr, root.right, 2 * i + 2, n)
return root
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
def preorder_traversal(root):
if root:
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
```
其中,`create_tree` 函数用于创建二叉树,`inorder_traversal`、`preorder_traversal` 和 `postorder_traversal` 分别实现了中序遍历、前序遍历和后序遍历。你可以按照以下步骤使用上述代码:
1. 创建一个无序列表 `arr`,里面包含了需要创建的二叉树的所有节点值,节点值可以是数字、字符串等;
2. 调用 `create_tree` 函数,传入 `arr`、`None`、0 和 `len(arr)`;
3. 调用 `inorder_traversal`、`preorder_traversal` 和 `postorder_traversal` 函数,分别遍历二叉树并输出遍历结果。
例如,以下是一个创建二叉树并遍历的示例:
```python
arr = [1, 2, 3, 4, 5, 6, 7]
root = create_tree(arr, None, 0, len(arr))
print('Inorder Traversal:', end=' ')
inorder_traversal(root)
print('\nPreorder Traversal:', end=' ')
preorder_traversal(root)
print('\nPostorder Traversal:', end=' ')
postorder_traversal(root)
```
输出结果为:
```
Inorder Traversal: 4 2 5 1 6 3 7
Preorder Traversal: 1 2 4 5 3 6 7
Postorder Traversal: 4 5 2 6 7 3 1
```
在使用这份代码的时候,你需要自己定义一个无序列表 `arr`,然后传入 `create_tree` 函数中进行创建二叉树。你也可以根据自己的需要修改 `create_tree` 函数的输入参数,例如可以将 `arr` 参数改为用户输入的列表。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](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)