我正在开展一个涉及以字典表示的二叉树的大学项目。我已经实现了检查这些树是否完整、完整和二叉树的函数，但是我的二叉树验证没有按预期工作。您能帮我找出错误吗？
class No:
def __init__(self, valor):
self.valor = valor
self.esquerda = None
self.direita = None
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:
no.esquerda = criar_arvore(definicao, filhos[0])
no.direita = criar_arvore(definicao, filhos[1])
return no
arvore_1 = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': None,
'E': None,
'F': None,
'G': None
}
arvore_2 = {
'A': ['B', 'C', 'D'],
'B': None,
'C': None,
'D': None
}
raiz_arvore_1 = criar_arvore(arvore_1, 'A')
raiz_arvore_2 = criar_arvore(arvore_2, 'A')
def pre_ordem(no):
if no is None:
return []
return [no.valor] + pre_ordem(no.esquerda) + pre_ordem(no.direita)
def em_ordem(no):
if no is None:
return []
return em_ordem(no.esquerda) + [no.valor] + em_ordem(no.direita)
def pos_ordem(no):
if no is None:
return []
return pos_ordem(no.esquerda) + pos_ordem(no.direita) + [no.valor]
def altura_arvore(no):
if no is None:
return -1
return 1 + max(altura_arvore(no.esquerda), altura_arvore(no.direita))
def verificar_arvore_binaria(no):
def verificar(no):
if no is None:
return True, None
if no.esquerda and no.direita:
return True, no.valor
if not (no.esquerda or no.direita):
return True, no.valor
if not no.esquerda:
return verificar(no.direita)
if not no.direita:
return verificar(no.esquerda)
return False, no.valor
binaria, _ = verificar(no)
return binaria
def verificar_arvore_cheia(no):
if no is None:
return True
if no.esquerda is None and no.direita is None:
return True
if no.esquerda is not None and no.direita is not None:
return verificar_arvore_cheia(no.esquerda) and verificar_arvore_cheia(no.direita)
return False
def verificar_arvore_completa(no, indice, total_nos):
if no is None:
return True
if indice >= total_nos:
return False
return (verificar_arvore_completa(no.esquerda, 2 * indice + 1, total_nos) and
verificar_arvore_completa(no.direita, 2 * indice + 2, total_nos))
def contar_nos(no):
if no is None:
return 0
return 1 + contar_nos(no.esquerda) + contar_nos(no.direita)
def analisar_arvore(raiz, nome):
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(raiz))
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")
analisar_arvore(raiz_arvore_2, "2")
控制台：
Árvore 1:
Pré-ordem: ['A', 'B', 'D', 'E', 'C', 'F', 'G']
Em ordem: ['D', 'B', 'E', 'A', 'F', 'C', 'G']
Pós-ordem: ['D', 'E', 'B', 'F', 'G', 'C', 'A']
Altura da árvore: 2
É uma árvore binária?: True
É uma árvore cheia?: True
É uma árvore completa?: True
Árvore 2:
Pré-ordem: ['A', 'B', 'C']
Em ordem: ['B', 'A', 'C']
Pós-ordem: ['B', 'C', 'A']
Altura da árvore: 1
É uma árvore binária?: True
É uma árvore cheia?: True
É uma árvore completa?: True
我预计它会在“Árvore 2”中出现：
É uma árvore binária?: False
É uma árvore cheia?: True
É uma árvore completa?: True
这里有几个问题：
当您将图的字典表示转换为二叉树（其中每个节点都有左属性和右属性）时，检查它是否是二叉树是没有意义的，因为当然它是：您创建了它作为一个整体。请注意：
Falseif由于所有验证函数都已假定具有左/右子节点的节点，因此它们不适用于节点可能具有三个以上子节点的一般情况。
尚不清楚中序遍历对于第二个输入意味着什么：“中序”的概念仅对于二叉树有明确的定义，而对于一般树则没有。您必须就该概念的某些概括达成一致。例如，您可以说内部节点在其第一个子节点之后和任何其他子节点之前被访问。
如果节点只有一个子节点，您的树创建函数将会出错。
对完整树的检查不正确。例如，对于这个二叉树，它将返回 True：
A
/ \
B C
/ \
D E
/ \
F G
我建议不要将输入字典转换为其他结构。该词典可以按原样使用。
这是一个可能的实现，直接使用字典表示：
tree1 = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': None,
'E': None,
'F': None,
'G': None
}
tree2 = {
'A': ['B', 'C', 'D'],
'B': None,
'C': None,
'D': None
}
def pre_order(tree, root):
def order(node):
yield node
for child in tree[node] or []:
yield from order(child)
return [] if root is None else list(order(root))
def in_order(tree, root):
def order(node):
if tree[node]:
yield from order(tree[node][0])
yield node
if tree[node]:
for child in tree[node][1:]:
yield from order(child)
return list(order(root)) if tree else []
def post_order(tree, root):
def order(node):
for child in tree[node] or []:
yield from order(child)
yield node
return list(order(root)) if tree else []
def tree_height(tree, root):
def height(node):
return 1 + max(map(height, tree[node] or []), default=-1)
return height(root) if tree else -1
def is_binary_tree(tree):
return not tree or all(not children or len(children) <= 2 for children in tree.values())
def is_full_tree(tree):
return not tree or len(set(len(children) if children else 0 for children in tree.values())) <= 2
def is_complete_tree(tree, root):
if not tree or len(tree) <= 1:
return True
degree = len(tree[root])
# perform a breadth-first traversal
q = [root]
at_bottom = False
for node in q:
if tree[node] and (len(tree[node]) > degree or at_bottom):
return False
if not tree[node] or len(tree[node]) < degree:
# As soon as one parent has not a complete set of children, no
# other parents (in BFS order) should have children
at_bottom = True
if tree[node]:
q.extend(tree[node])
return True
def count_nodes(tree):
return len(tree)
def analyse_tree(tree, name, root):
total_nodes = count_nodes(root)
print(f"Tree {name}:")
print("Pre-order:", pre_order(tree, root))
print("In-order:", in_order(tree, root))
print("Post-order:", post_order(tree, root))
print("Height of the tree:", tree_height(tree, root))
print("Is it a binary tree:", is_binary_tree(tree))
print("Is it a full tree:", is_full_tree(tree))
print("Is it a complete tree:", is_complete_tree(tree, root))
print()
analyse_tree(tree1, "1", "A")
analyse_tree(tree2, "2", "A")