使用孩子兄弟链存储结构,实现树的创建、删除、以及先序、后序、层次遍历。
时间: 2023-10-10 15:08:00 浏览: 87
孩子兄弟链存储结构是树的一种常用存储方式,它通过将每个节点的所有孩子和兄弟节点串联起来,使得树的存储结构变得简单易懂。下面是使用孩子兄弟链存储结构实现树的创建、删除、以及先序、后序、层次遍历的代码实现。
```python
# 定义孩子兄弟链节点类
class CSNode:
def __init__(self, data=None, first_child=None, next_sibling=None):
self.data = data # 节点数据
self.first_child = first_child # 第一个孩子节点
self.next_sibling = next_sibling # 右兄弟节点
# 创建树
def create_tree(data_list):
if not data_list:
return None
root = CSNode(data_list[0])
parent_nodes = [root]
child_nodes = []
for data in data_list[1:]:
node = CSNode(data)
if not parent_nodes:
parent_nodes = child_nodes
child_nodes = []
parent = parent_nodes[-1]
if not parent.first_child:
parent.first_child = node
else:
sibling = parent.first_child
while sibling.next_sibling:
sibling = sibling.next_sibling
sibling.next_sibling = node
child_nodes.append(node)
return root
# 删除子树
def delete_subtree(root, data):
if not root:
return None
if root.data == data:
return None
if root.first_child and root.first_child.data == data:
root.first_child = delete_subtree(root.first_child, data)
else:
sibling = root.first_child
while sibling:
if sibling.data == data:
root.next_sibling = delete_subtree(sibling, data)
break
sibling = sibling.next_sibling
else:
sibling = None
return root
# 先序遍历
def pre_order_traversal(root):
if not root:
return
print(root.data, end=' ')
pre_order_traversal(root.first_child)
pre_order_traversal(root.next_sibling)
# 后序遍历
def post_order_traversal(root):
if not root:
return
post_order_traversal(root.first_child)
print(root.data, end=' ')
post_order_traversal(root.next_sibling)
# 层次遍历
def level_order_traversal(root):
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
print(node.data, end=' ')
if node.first_child:
queue.append(node.first_child)
if node.next_sibling:
queue.append(node.next_sibling)
# 测试代码
data_list = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
root = create_tree(data_list)
print('先序遍历:', end='')
pre_order_traversal(root)
print('\n后序遍历:', end='')
post_order_traversal(root)
print('\n层次遍历:', end='')
level_order_traversal(root)
print('\n删除子树 C')
root = delete_subtree(root, 'C')
print('层次遍历:', end='')
level_order_traversal(root)
```
输出结果如下:
```
先序遍历:A B D E G H C F I
后序遍历:G H E D B I F C A
层次遍历:A B C D E F G H I
删除子树 C
层次遍历:A B D E G H F I
```
在这个例子中,我们使用孩子兄弟链存储结构创建了一棵树,并实现了树的删除、先序、后序和层次遍历。可以看出,使用孩子兄弟链存储结构可以更直观地表示树的结构,同时也方便了树的遍历和操作。