python - 带有搜索和删除功能的python二叉树遍历
问题描述
我创建了一个二叉树遍历项目。不幸的是,我对python有基本的了解。我正确地写了“preorder”、“inorder”和“postorder”。但我无法创建查找和删除节点功能。请帮忙。请检查下面的代码。请帮助创建这两个功能。谢谢
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def find(self, value):
if self.value == value:
return True
elif value < self.value and self.left:
return self.left.find(value)
elif value > self.value and self.right:
return self.right.find(value)
return False
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
def print_tree(self, traversal_type):
if traversal_type == "preorder":
return self.preorder_print(tree.root, "")
elif traversal_type == "inorder":
return self.inorder_print(tree.root, "")
elif traversal_type == "postorder":
return self.postorder_print(tree.root, "")
else:
print("Traversal type "+str(traversal_type)+" is not supported.")
def preorder_print(self, start, traversal):
# Root->Left->Right
if start:
traversal += (str(start.value)+"-")
traversal = self.preorder_print(start.left, traversal)
traversal = self.preorder_print(start.right, traversal)
return traversal
def inorder_print(self, start, traversal):
# Left->Root->Right
if start:
traversal = self.inorder_print(start.left, traversal)
traversal += (str(start.value) + "-")
traversal = self.inorder_print(start.right, traversal)
return traversal
def postorder_print(self, start, traversal):
# Left->Right->Root
if start:
traversal = self.postorder_print(start.left, traversal)
traversal = self.postorder_print(start.right, traversal)
traversal += (str(start.value) + "-")
return traversal
# Set up tree order
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
tree.root.right.left = Node(6)
tree.root.right.right = Node(7)
print("Preorder: " + tree.print_tree("preorder")) # 1-2-4-5-3-6-7
print("Inorder: " + tree.print_tree("inorder")) # 4-2-5-1-6-3-7
print("Postorder: " + tree.print_tree("postorder")) # 4-2-5-6-3-7-1
print(tree.root.find(1))
print(tree.root.find(2))
print(tree.root.find(3))
print(tree.root.find(4))
print(tree.root.find(5))
print(tree.root.find(6))
print(tree.root.find(7))
print(tree.root.find(8)) ```
解决方案
find 不起作用的原因是您设置的树不是二叉搜索树。在 BST 中,左侧的所有节点的值都低于根,而右侧的所有节点的值都更高。检查您构建的树。
这是删除节点的实现。
https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
推荐阅读
- python - 如何为这个 Jar 和 candy python 问题创建解决方案?
- php - Stripe Webhook 错误:警告:array_keys() 期望参数 1 是数组,给定字符串
- .htaccess - Mod Rewrite - 设置默认路径
- c# - 放气字符串 C#
- java - 在另一个 JFrame 上添加来自另一个 JTable 的所有行值 JTable 数据
- android - 使用 Google Play 计费库 2 的延迟订阅续订实时开发者通知
- javascript - 如何在 JavaScript 中对字符串进行数学运算?
- python - Pyqt5设计师试图将图片设置为按钮背景但得到“无效的样式表”
- spring-batch - 如何通过传递布尔标志来禁用或启用作业来控制所有按计划 cron 作业运行的春季批处理作业?
- python-3.x - 删除每行末尾的换行符和不需要的字符