0

Interactivepython上的 Tree 插入函数不正确吗？

向左插入：

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

我发现逻辑不正确，插入导致树损坏。

我尝试了以下（您可以在同一页面上运行代码）并查看验证。

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertLeft(r, [10, [11, [],[]], []])
insertRight(r,6)
insertRight(r,7)
print(r)

输出：

[3, 
    [
        [10, [11, [], []], []], 
            [5, [4, [], []], []], 
            []
    ], 
    [
        7, 
            [], 
            [6, [], []]
    ]
]
4

1 回答 1

0

结果符合这些功能的预期。以下：

insertLeft(r, [10, [11, [],[]], []])

...注入一个值作为根的左孩子。将赋予该新节点的值是您作为第二个参数提供的值。这个函数总是创建一个新节点（三元组），并且你已经给它一个树结构的值。

这在输出中看起来很奇怪，并且看起来结构已损坏，但事实并非如此。值[10, [11, [],[]], []]就是那个值——一个值——它不参与构建主树。

也许你想合并两棵树。但在这种情况下，您应该决定根左节点的子树应该发生什么。例如，您可以执行以下操作：

insertLeft(r, 11)
insertLeft(r, 10)

... 然后前一个子树 ( [5, [4, [], []], []]) 将成为值为 11 的节点的子节点。

简而言之，为了合并子树，您不能只将一个子树作为参数传递给insertLeft. 该方法仅用于注入具有一个特定值的单个节点。

于 2017-05-07T19:09:23.420 回答