gpt4 book ai didi

python - python中的二进制搜索树不起作用

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:53:54 27 4
gpt4 key购买 nike

class Node:
'''represents a new node in the BST'''
def __init__(self,key):
self.key=key
self.disconnect()
def disconnect(self):
self.left=None;
self.right=None;
self.parent=None;
def __str__(self):
return 'node with kay %s'%self.key

class BST:
def __init__(self):
self.root=None
def insert(self,t):
'''inserts a new element into the tree'''
self.find_place(self.root,t)

def find_place(self,node,key):
"""finds the right place of the element recursively"""
if node is None:
node=Node(key)
print node
else:
if node.key > key:
find_place(node.left,key)
else:
find_place(node.right,key)
def test():
'''function to test if the BST is working correctly'''

我写了上面的代码来实现二叉搜索树,但是插入方法没有按预期工作,它甚至无法添加根元素。我无法理解原因。

最佳答案

您实际上并没有向树中添加任何节点!

显式管理根节点的添加是最简单的,正如您在下面的 insert 中看到的那样。

一个 find_place 函数会,大概从名称中,返回父节点以及它是键的左插槽还是右插槽?我在下面创建了一个显式的 _do_insert 函数,它既可以遍历又可以执行插入。

从那时起,您需要遍历这棵树,每次查看您是否递归到一个分支,或者您是否到达了一个空槽,然后在此处添加新节点。

重构您的代码以将遍历树(以及执行添加、删除等)的责任放到 Node 类中可能很自然。

在下面的代码中,我忽略了添加一个已经在树中的键,我只是静静地退出:

def insert(self,t):
'''inserts a new element into the tree'''
if self.root is None:
self.root = Node(t)
else:
self._do_insert(self.root,t)

def _do_insert(self,parent,t):
if t > parent.key:
if parent.left is None:
parent.left = Node(t)
else:
self._do_insert(parent.left,t)
elif t < parent.key:
if parent.right is None:
parent.right = Node(t)
else:
self._do_insert(parent.right,t)
else:
# raise a KeyError or something appropriate?
pass

关于python - python中的二进制搜索树不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3078539/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com