插入到二叉搜索树

所以我必须将一个节点插入二叉搜索树。在我的入门级课程中，二叉搜索树被表示为链接列表，如下图所示的这个二叉树的 [4, [5, [0, [],[]], [2, [], []]], [1, [],[]]]：插入到二叉搜索树

this binary tree 。

（这不是一个二叉搜索树，只是一张二叉树，我有一张照片）。

所以插入一个节点到一棵树，我写了下面的递归代码：

def tree_node(key): 
    return [key, [],[]] 

def insert(bst,key): 
    if bst == []: 
     return tree_node(key) 
    if key < bst[0]: 
     return insert(bst[1],key) 
    else: 
     return insert(bst[2],key) 
    return bst

这只是返回虽然节点，而不是新的树节点

例如：

>>> insert([2, [1, [], []], [3, [], []]], 6) 
[6, [], []]

当它应该是：

>>> insert([2, [1, [], []], [3, [], []]], 6) 
[2, [1, [], []], [3, [], [6, [], []]]]

谢谢！

来源

2016-02-29 Samrose Ahmed

你永远不会将节点插入你的树中。看看你的基本情况 - 而不是将节点插入它应该是的，你只是简单地返回节点。 –

您需要更改基本情况。而不是返回新list，你需要修改你在获得通过的空单切片赋值可能是最简单的：

def insert(bst,key): 
    if bst == []: 
     bst[:] = tree_node(key) 
    elif key < bst[0]: 
     insert(bst[1],key) 
    else: 
     insert(bst[2],key)

因为这个函数修改树的地方，我不回来了。如果你想这样做，只需在最后重新添加return bst（但不是在递归步骤中，我们希望忽略那些返回值）。

来源

2016-02-29 02:51:03 Blckknght

只是为了向Samrose澄清，因为他似乎是Python的新手 - 因为值是通过引用传递的，所以'bst [：] = x'本质上是指在'bst'引用的列表中从头到尾替换值，并且在x中找到的值。因此，在这种情况下，递归函数在bst中找到叶节点，并用'tree_node'生成的新tree_node替换找到的空叶节点。 –

我会纠正它将用新节点的内容替换列表的*内容*（它是空的，所以它实际上不会删除任何内容）。它不会重新绑定任何变量名称。 – Blckknght

是的，这正是我想要得到的，很好的澄清。 –

变化return insert(bst[1],key)与bst[1] = insert(bst[1],key)（和类似的bst[2]）;这样你实际上插入了一些东西，并且会执行最后的return声明。

来源

2016-02-29 02:52:02

插入到二叉搜索树

回答

相关问题