编写一个程序实现二叉树的建立、遍历、求二叉树深度
时间: 2024-01-14 17:02:42 浏览: 42
好的,下面是Python实现二叉树的代码:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 建立二叉树
def buildTree():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
return root
# 先序遍历
def preorderTraversal(root):
if root:
print(root.val, end=' ')
preorderTraversal(root.left)
preorderTraversal(root.right)
# 中序遍历
def inorderTraversal(root):
if root:
inorderTraversal(root.left)
print(root.val, end=' ')
inorderTraversal(root.right)
# 后序遍历
def postorderTraversal(root):
if root:
postorderTraversal(root.left)
postorderTraversal(root.right)
print(root.val, end=' ')
# 求二叉树深度
def depth(root):
if not root:
return 0
left_depth = depth(root.left)
right_depth = depth(root.right)
return max(left_depth, right_depth) + 1
# 测试代码
root = buildTree()
print('先序遍历:')
preorderTraversal(root)
print('\n中序遍历:')
inorderTraversal(root)
print('\n后序遍历:')
postorderTraversal(root)
print('\n二叉树深度:', depth(root))
```
输出结果为:
```
先序遍历:
1 2 4 5 3 6 7
中序遍历:
4 2 5 1 6 3 7
后序遍历:
4 5 2 6 7 3 1
二叉树深度: 3
```
以上代码实现了二叉树的建立、遍历和求二叉树深度。其中,建立二叉树使用了前序遍历的方式,先建立根节点,然后建立左子树和右子树;遍历使用了递归的方式,先遍历左子树,然后访问根节点,最后遍历右子树;求深度使用了递归的方式,分别求左子树和右子树的深度,然后取最大值再加1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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_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)