请求排查二叉树验证函数错误——字典实现的Python二叉树项目

根本原因 #

1. 树构建时忽略多余子节点：criar_arvore函数仅处理每个节点子列表的前两个元素，丢弃多余的子节点。例如arvore_2中根节点A的第三个子节点D未被添加到树结构中，最终生成的树只有A的两个子节点B和C，符合二叉树定义，因此verificar_arvore_binaria返回True。
2. 二叉树验证函数逻辑无效：当前verificar_arvore_binaria函数的逻辑覆盖了所有可能的子节点数量情况（0、1、2个），最终总是返回True，无法检测任何无效情况。而由于No类仅定义了左右两个子节点指针，生成的树结构本身必然是二叉树，该函数实际上没有意义。

解决方案 #

方案1：在树构建阶段验证输入合法性

修改criar_arvore函数，检查每个节点的子节点数量是否超过2，若超过则抛出错误或标记树为无效：

def criar_arvore(definicao, valor_atual):
    if valor_atual is None:
        return None
    no = No(valor_atual)
    filhos = definicao.get(valor_atual, None)
    if filhos:
        # 检查子节点数量是否超过2
        if len(filhos) > 2:
            raise ValueError(f"节点 {valor_atual} 包含超过2个子节点，不符合二叉树定义")
        no.esquerda = criar_arvore(definicao, filhos[0])
        no.direita = criar_arvore(definicao, filhos[1])
    return no

这样构建arvore_2时会直接抛出错误，阻止无效树的生成。

方案2：直接验证原始字典的合法性

如果需要验证输入字典是否符合二叉树定义（每个节点最多2个子节点），可以新增一个针对字典的验证函数：

def verificar_arvore_binaria_dict(definicao):
    for no_valor, filhos in definicao.items():
        if filhos is not None and len(filhos) > 2:
            return False
    return True

然后修改analisar_arvore函数，传入原始字典并调用该函数：

def analisar_arvore(raiz, nome, definicao):
    total_nos = contar_nos(raiz)
    print(f"Árvore {nome}:")
    print("Pré-ordem:", pre_ordem(raiz))
    print("Em ordem:", em_ordem(raiz))
    print("Pós-ordem:", pos_ordem(raiz))
    print("Altura da árvore:", altura_arvore(raiz))
    print("É uma árvore binária?:", verificar_arvore_binaria_dict(definicao))
    print("É uma árvore cheia?:", verificar_arvore_cheia(raiz))
    print("É uma árvore completa?:", verificar_arvore_completa(raiz, 0, total_nos))
    print()

# 调用时传入原始字典
analisar_arvore(raiz_arvore_1, "1", arvore_1)
analisar_arvore(raiz_arvore_2, "2", arvore_2)

此时arvore_2的验证结果会正确返回False。

优化无效的验证函数

由于基于No类构建的树结构必然是二叉树，原verificar_arvore_binaria函数可以简化为直接返回True，或者删除该函数（如果不需要保留）：

def verificar_arvore_binaria(no):
    return True

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