实现二叉树的基本操作: (1)实现二叉树的创建功能; (2)实现遍历功能,先序,打印出遍历序列; (3)实现“结点的度”的统计功能;输出每个结点的度; (4)计算树的深度。 用于测试的二叉树为:11,13,12,22,25,26,17, ,9,10, ,3
时间: 2023-09-14 15:11:25 浏览: 27
好的,下面我来为您演示如何实现二叉树的基本操作。
首先,我们需要定义二叉树的结点,包括结点值、左子树和右子树。
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
```
接下来,我们可以通过递归的方式创建二叉树。具体实现如下:
```python
def build_tree(arr, index):
if index >= len(arr) or arr[index] is None:
return None
root = Node(arr[index])
root.left = build_tree(arr, 2 * index + 1)
root.right = build_tree(arr, 2 * index + 2)
return root
```
其中,参数 `arr` 表示二叉树的结点值列表,`index` 表示当前结点在列表中的下标。
接下来,我们可以实现二叉树的先序遍历,并打印出遍历序列。
```python
def preorder(root):
if not root:
return []
res = [root.val]
res += preorder(root.left)
res += preorder(root.right)
return res
arr = [11,13,12,22,25,26,17,None,9,10,None,3]
root = build_tree(arr, 0)
print(preorder(root)) # [11, 13, 22, 25, 17, 9, 3, 12, 26, 10]
```
接下来,我们可以统计每个结点的度,并输出结果。
```python
def get_degree(root):
if not root:
return {}
degree = {}
degree[root.val] = 0
if root.left:
degree[root.val] += 1
degree.update(get_degree(root.left))
if root.right:
degree[root.val] += 1
degree.update(get_degree(root.right))
return degree
print(get_degree(root)) # {11: 2, 13: 2, 12: 1, 22: 0, 25: 1, 26: 0, 17: 2, 9: 0, 10: 0, 3: 0}
```
最后,我们可以计算二叉树的深度。
```python
def get_depth(root):
if not root:
return 0
return max(get_depth(root.left), get_depth(root.right)) + 1
print(get_depth(root)) # 4
```
以上就是实现二叉树的基本操作的全部内容。
相关推荐
![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_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)