python二叉搜索树遍历
时间: 2024-08-12 16:03:22 浏览: 22
在Python中,二叉搜索树(Binary Search Tree,BST)是一种常见的数据结构,它的每个节点都包含一个键值,并且左子树的所有节点的键都小于该节点的键,右子树的所有节点的键都大于该节点的键。遍历BST主要有三种方式:
1. **前序遍历(Preorder Traversal)**:先访问根节点,然后递归地遍历左子树,最后遍历右子树。Python代码示例:
```python
def preorder_traversal(root):
if root is not None:
print(root.val) # 访问根节点
preorder_traversal(root.left) # 遍历左子树
preorder_traversal(root.right) # 遍历右子树
```
2. **中序遍历(Inorder Traversal)**:先递归地遍历左子树,然后访问根节点,最后遍历右子树。对于排序后的BST,这将返回一个升序序列。Python代码:
```python
def inorder_traversal(root):
if root is not None:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
```
3. **后序遍历(Postorder Traversal)**:先递归地遍历左子树和右子树,最后访问根节点。Python实现:
```python
def postorder_traversal(root):
if root is not None:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val)
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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_column_c1.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)