一棵树采用孩子链存储结构/或长子兄弟链存储结构(任选一种),尝试用python编程实现: (1) 创建一棵树 (2) 设计一个算法求高度 (3) 设计一个算法实现树的层次遍历 (4) 设计两个算法实现先根遍历和后根遍历
时间: 2024-02-05 11:02:51 浏览: 79
以孩子链存储结构为例,代码实现如下:
```python
class TreeNode:
def __init__(self, data):
self.data = data
self.child = []
class Tree:
def __init__(self):
self.root = None
def create_tree(self, data_list):
node_list = []
for data in data_list:
node_list.append(TreeNode(data))
self.root = node_list[0]
for i in range(len(node_list)):
children = []
for j in range(i+1, len(node_list)):
if node_list[j].data in node_list[i].child:
children.append(node_list[j])
node_list[i].child = children
def get_height(self, node):
if not node.child:
return 0
else:
return max(self.get_height(child) for child in node.child) + 1
def level_order_traversal(self):
if not self.root:
return []
queue = [self.root]
res = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.pop(0)
level.append(node.data)
for child in node.child:
queue.append(child)
res.append(level)
return res
def preorder_traversal(self, node, res):
if not node:
return
res.append(node.data)
for child in node.child:
self.preorder_traversal(child, res)
def postorder_traversal(self, node, res):
if not node:
return
for child in node.child:
self.postorder_traversal(child, res)
res.append(node.data)
```
其中,`TreeNode` 表示树节点,包含节点数据和孩子列表;`Tree` 表示树,包含根节点和创建树、求高度、层次遍历、先根遍历、后根遍历等方法。
具体实现:
1. `create_tree` 方法用于创建一棵树,输入数据列表,先将每个数据转化为一个 `TreeNode` 对象,然后通过判断每个节点的孩子节点建立孩子列表关系。
2. `get_height` 方法用于求树的高度,输入当前节点,如果没有孩子则高度为 0,否则遍历孩子节点,返回最大高度加 1。
3. `level_order_traversal` 方法用于层次遍历树,使用队列辅助遍历,先将根节点入队,然后依次取出队列中的节点,将其孩子节点入队,并记录每一层的数据。
4. `preorder_traversal` 方法用于先根遍历树,使用递归实现,先记录当前节点的数据,然后遍历孩子节点。
5. `postorder_traversal` 方法用于后根遍历树,使用递归实现,先遍历孩子节点,然后记录当前节点的数据。
使用示例:
```python
data_list = [1, 2, 3, 4, 5, 6, 7]
tree = Tree()
tree.create_tree(data_list)
print("树的高度为:", tree.get_height(tree.root))
print("树的层次遍历为:", tree.level_order_traversal())
preorder_res = []
tree.preorder_traversal(tree.root, preorder_res)
print("树的先根遍历为:", preorder_res)
postorder_res = []
tree.postorder_traversal(tree.root, postorder_res)
print("树的后根遍历为:", postorder_res)
```
阅读全文