请使用一种程序设计语言改写一般树的宽度优先遍历算法,要求能够计算出 每个顶点的层次
时间: 2023-06-09 14:04:59 浏览: 72
好的,我可以使用 Python 语言来改写宽度优先遍历算法,并计算每个顶点的层次。下面是代码示例:
```python
from collections import deque
#定义一般树节点类,包括当前节点值、子节点列表、以及当前节点的层次(level)
class TreeNode:
def __init__(self, val=0, children=None, level=0):
self.val = val
self.children = children if children is not None else []
self.level = level
#定义树的宽度优先遍历函数,并计算每个节点的层次
def bfs(root):
if not root:
return []
queue = deque([root])
res = []
while queue:
size = len(queue)
for i in range(size):
cur = queue.popleft()
res.append(cur.val)
cur.level = i #记录当前节点的层数
queue.extend(cur.children)
return res
#构建一般树
root = TreeNode(1, [TreeNode(2, [TreeNode(4), TreeNode(5)]), TreeNode(3, [TreeNode(6, [TreeNode(8), TreeNode(9)]), TreeNode(7)])])
#进行宽度优先遍历,并打印每个节点的值及对应的层数(层次)
result = bfs(root)
for i in range(len(result)):
print("节点值为{}的层数(level)为{}".format(result[i], root.children[i].level))
```
以上代码可以针对任意一般树进行宽度优先遍历,并计算每个节点的层数。