二叉树的宽度

Question

我们如何确定二叉树的广度a。

一个简单的 bin 树

上面树的宽度是4

Answer 1

您可以使用递归函数，该函数 return 给定节点的两个值：该节点处子树向左的范围（负数或零）和向右的范围（零或正数）。因此，对于问题中给出的示例树，它将 return -1 和 3.

当您知道左侧 child 和右侧 child 的范围时，找到这些范围很容易。这就是递归开始的地方，它实际上代表了一个 depth-first 遍历。

下面是该函数在 Python 中的样子：

def extents(tree):
    if not tree:
        # If a tree with just one node has extents 0 and 0, then "nothing" should
        #  have a negative extent to the right and a positive on the left, 
        #  representing a negative breadth
        return 1, -1
    leftleft, leftright = extents(tree.left)
    rightleft, rightright = extents(tree.right)
    return min(leftleft-1, rightleft+1), max(leftright-1, rightright+1)

广度就是上述函数return两个extents之差加1（计入根节点）：

def breadth(tree):
    leftextent, rightextent = extents(tree)
    return rightextent-leftextent+1

带有示例树的完整 Python 代码，有 6 个节点，作为输入：

from collections import namedtuple
Node =  namedtuple('Node', ['left', 'right'])

def extents(tree):
    if not tree:
        return 1, -1
    leftleft, leftright = extents(tree.left)
    rightleft, rightright = extents(tree.right)
    return min(leftleft-1, rightleft+1), max(leftright-1, rightright+1)

def breadth(tree):
    left, right = extents(tree)
    return right-left+1

# example tree as given in question
tree = Node(
    Node(
        None,
        Node(None, Node(None, Node(None, None)))
    ),
    Node(None, None)
)

print(breadth(tree)) # outputs 4

二叉树的宽度

breadth of a binary tree

algorithm

tree

binary-tree