所以我必须将一个节点插入二叉搜索树。在我的入门课程中,二进制搜索树以链接列表(例如)的形式表示,[4, [5, [0, [],[]], [2, [], []]], [1, [],[]]]
如下图所示:
。
(这不是二进制搜索树,只是我有图片的二进制树)。
因此,为了将节点插入树中,我编写了以下递归代码:
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, [], []]]]
谢谢!
您需要更改基本情况。无需返回new 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
在末尾重新添加(而不是在递归步骤中,我们想忽略那些返回值)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句