在Python中搭建一个树结构可以通过定义节点类和树类来实现。下面是一个简单的例子,展示了如何创建一个树结构:
```python
from collections import deque
定义一个节点类
class Node:
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
定义一个树类
class Tree:
def __init__(self, root=None):
self.root = root
利用层序遍历向树中添加元素
def add(self, elem):
node = Node(elem)
if self.root is None:
self.root = node
else:
queue = deque()
queue.append(self.root)
while queue:
cur_node = queue.popleft()
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
层序遍历
def level_order_traversal(self):
if self.root is None:
return []
queue = deque([self.root])
result = []
while queue:
node = queue.popleft()
result.append(node.elem)
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
return result
使用示例
if __name__ == "__main__":
tree = Tree()
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
print(tree.level_order_traversal()) 输出: [1, 2, 3, 4, 5]
这个例子中,`Node` 类表示树的节点,包含元素值 `elem` 和左右子节点 `lchild` 和 `rchild`。`Tree` 类表示整棵树,包含一个根节点 `root`,并提供添加元素的方法 `add` 和层序遍历的方法 `level_order_traversal`。
您可以根据需要扩展这些类,添加更多的功能,比如删除节点、查找节点等。如果您有更具体的需求或问题,请告诉我,我会尽力帮助您