二叉树宽度优先遍历python代码

以下是二叉树宽度优先遍历的Python代码：

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

def bfs(root):
    result = []
    if not root:
        return result
    queue = [root]
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

以上代码可以遍历二叉树，并返回一个包含每个层级节点值的列表。

相关问题

创建名为shixun2_3.py的文件，在文件中定义两个类，一个是二叉树的结点类，该类包含结点的相关信息（如结点的值和左、右子树）；另一个是二叉树的类，该类包含二叉树的定义及其宽度优先遍历操作。请通过以下步骤测试二叉树宽度优先遍历算法的实现是否正确。 ⑴初始化一个结点。 ⑵以⑴中结点作为根结点并使用链式存储结构，用循环体递归创建一棵二叉树，输入quit停止生成树。 ⑶对二叉树执行层次遍历，并将所得序列输出。

以下是代码实现：

class BinaryTreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
        
    def createTree(self):
        val = input("请输入结点的值，quit停止输入: ")
        if val == "quit":
            return
        self.root = BinaryTreeNode(val)
        queue = []
        queue.append(self.root)
        while queue:
            node = queue.pop(0)
            left_val = input("请输入" + node.val + "的左子结点的值，quit停止输入: ")
            if left_val != "quit":
                node.left = BinaryTreeNode(left_val)
                queue.append(node.left)
            right_val = input("请输入" + node.val + "的右子结点的值，quit停止输入: ")
            if right_val != "quit":
                node.right = BinaryTreeNode(right_val)
                queue.append(node.right)
        
    def levelOrderTraversal(self):
        if not self.root:
            return []
        res = []
        queue = [self.root]
        while queue:
            level = []
            for i in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)
        return res

以下是测试代码：

tree = BinaryTree()
tree.createTree()
print(tree.levelOrderTraversal())

在运行测试代码时，按照提示输入结点的值和左右子结点的值，最后输入quit停止输入。程序会输出层次遍历后的二叉树序列。

求输出二叉树的宽度的python代码

下面是输出二叉树宽度的Python代码：

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def width(root):
    if not root:
        return 0
    
    max_width = 0
    level = [(root, 0)]
    
    while level:
        cur_level_width = level[-1][1] - level[0][1] + 1
        max_width = max(max_width, cur_level_width)
        next_level = []
        for node, pos in level:
            if node.left:
                next_level.append((node.left, pos * 2))
            if node.right:
                next_level.append((node.right, pos * 2 + 1))
        level = next_level
    
    return max_width

# 测试代码
root = Node(1, Node(3, Node(5), Node(3)), Node(2, None, Node(9)))
print(width(root))  # 输出 4

解释：

- `width` 函数接受一个二叉树的根节点 `root`，返回二叉树的宽度。
- 首先判断树是否为空，若为空，则返回 0。
- 定义最大宽度 `max_width` 为 0，定义一个列表 `level`，当前层的节点和它们的位置信息 `(node, pos)` 存储在该列表中，初始时，`level` 中只有根节点 `root` 和它的位置 0。
- 进入循环，判断当前层的宽度 `cur_level_width` 并更新最大宽度 `max_width`。
- 定义一个空列表 `next_level`，遍历 `level` 中的所有节点，对于每个节点，如果它有左子节点，则将左子节点和它的位置信息 `(node.left, pos * 2)` 存储到 `next_level` 中；如果它有右子节点，则将右子节点和它的位置信息 `(node.right, pos * 2 + 1)` 存储到 `next_level` 中。
- 更新 `level` 为 `next_level`，继续循环。
- 循环结束后，返回最大宽度 `max_width`。