若一棵树采用孩子链存储结构t存储,用python设计一个算法求其高度
时间: 2023-06-15 10:04:10 浏览: 51
以下是用Python实现的求树高度的算法:
```python
class TreeNode:
def __init__(self, value, children=[]):
self.value = value
self.children = children
def get_height(root):
if not root:
return 0
if not root.children:
return 1
max_height = 0
for child in root.children:
child_height = get_height(child)
if child_height > max_height:
max_height = child_height
return max_height + 1
```
其中,`TreeNode`类表示树节点,包含一个值和一个子节点列表。`get_height`函数用递归的方式求树的高度,对于每个节点,遍历其子节点列表,求出子节点的高度,并取其中最大值,最后加一即为当前节点的高度。当遍历到叶子节点时,返回1,表示高度为1。当根节点为None时,返回0,表示高度为0。
使用示例:
```python
# 构建一棵树
root = TreeNode(1, [
TreeNode(2, [
TreeNode(4),
TreeNode(5, [
TreeNode(7),
TreeNode(8)
])
]),
TreeNode(3, [
TreeNode(6)
])
])
# 求树高度
height = get_height(root)
print(height) # 输出 4
```
这棵树的高度为4。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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_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)