python - 双向二叉搜索树?
问题描述
我试图实施 BST。到目前为止,它只根据 BST 属性(左-下,右-大)添加键。虽然我以不同的方式实现它。
这就是我认为 BST 应该是的样子
我如何实施我的 BST
问题是它是否是 BST 的正确实施?(我在双面 BST 中看到它的方式会更容易搜索、删除和插入)
import pdb;
class Node:
def __init__(self, value):
self.value=value
self.parent=None
self.left_child=None
self.right_child=None
class BST:
def __init__(self,root=None):
self.root=root
def add(self,value):
#pdb.set_trace()
new_node=Node(value)
self.tp=self.root
if self.root is not None:
while True:
if self.tp.parent is None:
break
else:
self.tp=self.tp.parent
#the self.tp varible always is at the first node.
while True:
if new_node.value >= self.tp.value :
if self.tp.right_child is None:
new_node.parent=self.tp
self.tp.right_child=new_node
break
elif self.tp.right_child is not None:
self.tp=self.tp.right_child
print("Going Down Right")
print(new_node.value)
elif new_node.value < self.tp.value :
if self.tp.left_child is None:
new_node.parent=self.tp
self.tp.left_child=new_node
break
elif self.tp.left_child is not None:
self.tp=self.tp.left_child
print("Going Down Left")
print(new_node.value)
self.root=new_node
newBST=BST()
newBST.add(9)
newBST.add(10)
newBST.add(2)
newBST.add(15)
newBST.add(14)
newBST.add(1)
newBST.add(3)
编辑:我使用了 while 循环而不是递归。有人可以详细说明为什么在这种特殊情况下和一般情况下使用 while 循环而不是递归是一个坏主意吗?
解决方案
偶尔会使用带有父链接的 BST。
好处不是链接使搜索或更新更容易(它们实际上并非如此),而是您可以在任何给定节点之前或之后插入,或者从该节点向前或向后遍历,而无需从根搜索.
使用指向节点的指针来表示树中的位置而不是完整路径变得很方便,即使树包含重复项,并且该位置在其他地方执行更新或删除时仍然有效。
例如,在抽象数据类型中,这些属性可以很容易地提供不会因突变而失效的迭代器。
推荐阅读
- java - Servlet 中的 Web 应用程序旁边的 Restful Web 服务
- sql - 程序未运行
- python - 将文件名保存在 numpy 文件 (.npy) 中
- python - 每个 PowerShell 调用 Python 脚本并传递 PSObject 并返回解析的数据
- python - 运行这个 django 项目,但它在 manage.py 中向我显示了这个错误
- c# - 登录后无法执行 GET 请求
- python - 使用 SQLAlchemy 在 Flask 中创建表不起作用
- react-day-picker - 如何在 React 日期选择器中使用公共方法“显示月份”在日历中显示给定月份?
- delphi - 如何在 OpenSSL 中加密 TMemoryStream 中的数据?
- php - 如何使用 PHP 更新 oracle 上的 CLOB 列