假设树上每个节点所含的数据元素为一个字母,并且以孩子链表为树的存储结构,试写一个按凹入表方式打印一棵树的算法
时间: 2024-03-25 14:38:44 浏览: 25
以下是一个按凹入表方式打印一棵树的算法的示例代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
def print_tree(root):
if not root:
return
# 初始化凹入表
indent_table = []
stack = [(root, 0, 0)]
prev_level = 0
while stack:
node, level, child_idx = stack.pop()
# 如果当前层级不同于前一层级,则添加一个新的缩进
if level != prev_level:
indent_table.append('\n' + ' ' * level)
# 将当前节点的值添加到凹入表中
indent_table.append(node.val)
# 将当前节点的所有孩子节点添加到堆栈中
if node.children:
for i in range(len(node.children) - 1, -1, -1):
stack.append((node.children[i], level + 1, i))
prev_level = level
# 打印凹入表
print(''.join(indent_table))
```
该算法通过一个堆栈来遍历树,同时维护一个凹入表。在遍历每个节点时,将节点的值添加到凹入表中,并将该节点的所有孩子节点添加到堆栈中。在堆栈中,每个节点都用三元组表示:节点本身、节点所在的层级和节点在其父节点孩子列表中的索引。通过这个三元组,算法可以在凹入表中正确地缩进每个节点。最后,算法将凹入表打印出来,即可按凹入表方式打印一棵树。