python - 在树python中插入一个新值
问题描述
我有一棵像这样的树:
tree = [[[None,1,None],2,[None,3,None]],4,[None,6,[None,7,None]]]
数字代表每个节点的根,none 代表没有值的子节点。
例如,主根是 4,[[None,1,None],2,[None,3,None]] 是左边的子树,这个 [None,6,[None,7,None]]他是右边的子树。左侧子树上的主根是 2 等等……
我的问题是我想在这棵树中插入一个值。
例如我想添加值 5,这就是我想要的:
tree = [[[None, 1, None], 2, [None, 3, None]], 4, [[None, 5, None], 6, [None, 7, None]]]
我的函数有两个参数,树和整数相加,我需要使用递归函数,例如这是我开始的:
def insert(tree,int):
cur = tree
prev = None
while cur != None:
prev = cur
if int < cur[1]:
cur = cur[0]
else :
cur = cur[2]
提前致谢
解决方案
既然你提到了递归,这里有一个使用递归的解决方案:
def insert_node(root, node):
if root == [None]: #corner case of an empty tree
root.append(node)
root.append(None) #now root will be : [None, node, None]
return
if node <= root[1]: #we need to go left
if root[0] == None:
root[0] = [None, node, None]
return
else:
insert_node(root[0], node)
else: #we need to go right
if root[2] == None:
root[2] = [None, node, None]
return
else:
insert_node(root[2], node)
测试解决方案:
tree = [None] #starting with an empty tree
insert_node(tree, 4)
insert_node(tree, 2)
insert_node(tree, 1)
insert_node(tree, 3)
insert_node(tree, 6)
insert_node(tree, 7)
print(tree)
该函数递归地遍历树,直到到达插入节点的正确位置。由于它是二叉搜索树,我们必须保证一个节点左边的任何孩子都应该小于该节点,而右边的任何孩子都应该大于该节点。这就是为什么我们根据新节点与遍历的当前根的比较来左/右。
推荐阅读
- java - 如何在 if 块中更新实例变量?
- json - 我需要与 Yasson 绑定 JSON 的 getter 吗?
- excel - 输入新值时,我的 excel 的单元格值不会更新
- python - 在多输出随机森林回归器中获取特征重要性
- reactjs - 为什么我的图像可以在本地工作,但不能在我的网络服务器上工作
- angular - 如何在第二个请求中使用来自 concatMap 的第一个响应
- python - Python 与 3 个列表的交集
- javascript - React 中的 Swiper 初始化
- python - 在 Python 中暂停非迭代进程
- javascript - 如何使用 axios(或 fetch)下载 mp4 文件并将其提供给