已知一颗树的节点间关系,请编程实现该树的先根遍历。 输入 若干行,每行描述了一组双亲节点和孩子节点的关系序偶对(每个节点用不同的大写字母表示,节点小于26个)。且树的度小于5。 输出 该树的先根遍历序列,序列中每个字母用空格隔开。 样例输入 复制 B E B F A B A C 样例输出 复制 A B E F C
时间: 2024-03-14 20:44:58 浏览: 110
这是一道树的遍历问题,可以使用递归或栈来实现。这里我选择使用递归来实现。
首先需要将输入的关系序偶对转换为树的数据结构。这里可以使用字典来存储每个节点和它的孩子节点。具体实现如下:
```python
tree = {}
for line in input_lines:
parent, child = line.strip().split()
if parent not in tree:
tree[parent] = []
tree[parent].append(child)
```
接下来实现先根遍历的递归函数。对于每个节点,先输出它的值,然后递归遍历它的每个孩子节点。具体实现如下:
```python
def pre_order_traversal(node):
print(node, end=' ')
if node in tree:
for child in tree[node]:
pre_order_traversal(child)
```
最后从根节点开始调用先根遍历的递归函数即可。完整代码如下:
```python
tree = {}
for line in input_lines:
parent, child = line.strip().split()
if parent not in tree:
tree[parent] = []
tree[parent].append(child)
def pre_order_traversal(node):
print(node, end=' ')
if node in tree:
for child in tree[node]:
pre_order_traversal(child)
root = [node for node in tree.keys() if node not in sum(tree.values(), [])][0]
pre_order_traversal(root)
```
其中,`root` 是树的根节点,它是那个没有父亲节点的节点。这里使用列表推导式来找到根节点。