求可渲染满二叉树为PNG的算法（Python优先，解决节点重叠）

需求概述 #

我有一棵每个节点恰好包含0或2个子节点的二叉树，需要将其渲染为PNG格式图像，要求：

• 节点渲染为包含多行文本的固定大小方框
• 所有节点使用相同尺寸的边界框
• 排版遵循经典二叉树布局：同层节点水平对齐，节点间无重叠，层级间垂直间距均匀（类似15个节点的标准完全二叉树排版样式）
• 优先提供Python解决方案

现有实现的问题 #

我尝试过ChatGPT生成的matplotlib代码，但无法调整节点间距避免重叠。现有代码如下：

import matplotlib.pyplot as plt

BOX_WIDTH = 2
BOX_HEIGHT = 2


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

    def get_content(self):
        box_props = dict(boxstyle='square', facecolor='white', edgecolor='black')

        value = self.val
        lines = ['Line 1asdasdasd', 'Line 2', 'Line 3']

        text = '\n'.join(lines)
        content = dict(value=value, text=text, box_props=box_props)

        return content


def plot_tree(node, x, y, parent_x=None, parent_y=None, x_offset=1., y_offset=1.):
    # Get node content
    if node is None:
        return

    content = node.get_content()

    # Draw box containing lines of text
    r = plt.text(x, y, content['text'], bbox=content['box_props'], ha='center', va='center')

    # Plot edge
    if parent_x is not None and parent_y is not None:
        plt.plot([parent_x, x], [parent_y, y], linewidth=1, color='black')

    # Plot left and right subtree with adjusted coordinates
    plot_tree(node.left, x - x_offset, y - y_offset, x, y, x_offset / 2, y_offset)

    plot_tree(node.right, x + x_offset, y - y_offset, x, y, x_offset / 2, y_offset)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

root.right.right.left = Node(2)
root.right.right.right = Node(3)
root.right.right.left.left = Node(4)
root.right.right.left.right = Node(5)
root.right.right.right.left = Node(6)
root.right.right.right.right = Node(7)

plt.figure()
plot_tree(root, 0, 0)
# plt.axis('off')
plt.show()

当前实现的问题：深层节点的方框互相挤压重叠，无法清晰展示所有节点内容。

改进的Python解决方案 #

核心问题在于原代码递归时直接将x_offset减半，导致深层节点的水平空间不足。正确的做法是先遍历二叉树，按层级计算每个节点的准确坐标，确保节点间的间距足够容纳固定尺寸的方框。

完整代码 #

import matplotlib.pyplot as plt

# 节点方框的固定尺寸（绘图坐标单位）
BOX_WIDTH = 1.2
BOX_HEIGHT = 1.0
# 节点间的最小水平间距
NODE_SPACING = 0.3
# 层级间的垂直间距
LEVEL_SPACING = 2.0

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        # 存储计算后的坐标和层级信息
        self.x = 0
        self.y = 0
        self.level = 0

    def get_content(self):
        """返回节点的多行文本内容和方框样式"""
        box_props = dict(boxstyle='square,pad=0.3', facecolor='white', edgecolor='black')
        # 自定义多行文本示例
        lines = [f'节点值: {self.val}', 'Line 1', 'Line 2', 'Line 3']
        text = '\n'.join(lines)
        return text, box_props

def calculate_node_positions(root):
    """按层级遍历，计算所有节点的坐标"""
    # 按层级存储节点
    levels = []
    queue = [(root, 0)]
    while queue:
        node, level = queue.pop(0)
        if level >= len(levels):
            levels.append([])
        levels[level].append(node)
        node.level = level
        if node.left:
            queue.append((node.left, level + 1))
        if node.right:
            queue.append((node.right, level + 1))
    
    # 为每一层分配均匀的水平坐标
    for level_idx, nodes in enumerate(levels):
        # 计算当前层的总宽度，确保节点间间距足够
        total_width = (len(nodes)-1)*(BOX_WIDTH + NODE_SPACING) + BOX_WIDTH
        # 从中心向两侧分配坐标，根节点位于x=0位置
        start_x = -total_width / 2 + BOX_WIDTH / 2
        for i, node in enumerate(nodes):
            node.x = start_x + i*(BOX_WIDTH + NODE_SPACING)
            node.y = -level_idx * LEVEL_SPACING  # 从上到下排列层级

def plot_binary_tree(root):
    """绘制二叉树并导出为PNG"""
    calculate_node_positions(root)
    fig, ax = plt.subplots(figsize=(12, 8))
    ax.set_aspect('equal')
    ax.axis('off')

    # 先绘制父子连线（避免被节点方框覆盖）
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node.left:
            ax.plot([node.x, node.left.x], [node.y, node.left.y], color='black', linewidth=1)
            queue.append(node.left)
        if node.right:
            ax.plot([node.x, node.right.x], [node.y, node.right.y], color='black', linewidth=1)
            queue.append(node.right)
    
    # 绘制所有节点的方框和文本
    queue = [root]
    while queue:
        node = queue.pop(0)
        text, box_props = node.get_content()
        ax.text(node.x, node.y, text, bbox=box_props, ha='center', va='center', fontsize=10)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    # 调整图边界，确保所有节点完整显示
    all_nodes = [node for level in calculate_node_positions.__closure__[0].cell_contents for node in level]
    min_x = min(node.x - BOX_WIDTH/2 for node in all_nodes)
    max_x = max(node.x + BOX_WIDTH/2 for node in all_nodes)
    min_y = min(node.y - BOX_HEIGHT/2 for node in all_nodes)
    max_y = max(node.y + BOX_HEIGHT/2 for node in all_nodes)
    ax.set_xlim(min_x - NODE_SPACING, max_x + NODE_SPACING)
    ax.set_ylim(min_y - LEVEL_SPACING/2, max_y + LEVEL_SPACING/2)

    # 导出为高分辨率PNG
    plt.savefig('binary_tree.png', dpi=300, bbox_inches='tight')
    plt.show()

# 测试用例
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.right.right.left = Node(2)
    root.right.right.right = Node(3)
    root.right.right.left.left = Node(4)
    root.right.right.left.right = Node(5)
    root.right.right.right.left = Node(6)
    root.right.right.right.right = Node(7)

    plot_binary_tree(root)

关键改进点 #

• 层级化坐标计算：先按层级遍历所有节点，再为每一层分配均匀的水平坐标，确保节点间的间距大于等于方框宽度+最小间距，彻底避免重叠
• 绘制顺序优化：先绘制父子连线，再绘制节点方框，避免连线被节点覆盖
• 固定节点尺寸：所有节点使用统一的方框样式和尺寸，符合需求
• PNG导出：直接生成高分辨率PNG图像，满足输出要求

内容的提问来源于stack exchange，提问作者Michael Pacheco