Python 中二叉搜索树的深度
Depth of a Binary Search Tree in Python
在我的二叉搜索树中,我正在制作一个深度函数,它会告诉用户他们插入的树的深度是多少。此功能对于我从最大深度节点删除节点的独特删除功能至关重要。我想我知道问题到底出在哪里,但我不确定。
这是我一直收到的错误。
C:\Python33\python.exe "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py"
Traceback (most recent call last):
PRE-ORDER TRANSVERSE:
File "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py", line 19, in <module>
4
print("The max depth of the tree is,", a.height(tree),"nodes deep.")
2
File "C:\Users\koopt_000\Desktop\College\Sophomore Semester 2\Computer Science 231\Chapter7\BinarySearchTree.py", line 245, in height
1
3
7
6
5
10
None
IN-ORDER TRANSVERSE:
1
2
3
4
5
6
7
10
None
POST-ORDER TRANSVERSE:
1
return max(BST.height(root.left), BST.height(root.right)) + 1
3
TypeError: height() missing 1 required positional argument: 'root'
2
5
6
10
7
4
None
Process finished with exit code 1
现在我认为我的问题出现在这段代码中:
return max(BST.height(root.left), BST.height(root.right)) + 1
我相信这句话是导致它的原因,因为它让我调用 BST 函数,高度函数已经在其中 'work'。我简单地尝试了"height.(root.left)",这没有用,因为它说没有全局变量高度。事实并非如此我不相信。
这是我的函数的完整代码列表,从我的树节点开始,然后是我的 BST 文件(主要),然后是我的测试代码。
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
self.item = data
self.left = left
self.right = right
def __str__(self):
return str(self.item)
from TreeNode import TreeNode
class BST(object):
#------------------------------------------------------------
def __init__(self):
"""create empty binary search tree
post: empty tree created"""
self.root = None
self.size = 0
def delete(self, item):
"""remove item from binary search tree
post: item is removed from the tree"""
self.root = self._subtreeDelete(self.root, item)
#------------------------------------------------------------
def _subtreeDelete(self, root, item):
if root is None: # Empty tree, nothing to do
return None
if item < root.item: # modify left
root.left = self._subtreeDelete(root.left, item)
elif item > root.item: # modify right
root.right = self._subtreeDelete(root.right, item)
else: # delete root
if root.left is None: # promote right subtree
root = root.right
elif root.right is None: # promote left subtree
root = root.left
else:
# root node can't be deleted, overwrite it with max of
# left subtree and delete max node from the subtree
root.item, root.left = self._subtreeDelMax(root.left)
return root
def _subtreeDelMax(self, root):
if root.right is None: # root is the max
return root.item, root.left # return max and promote left subtree
else:
# max is in right subtree, recursively find and delete it
maxVal, root.right = self._subtreeDelMax(root.right)
return maxVal, root
def height(self, root):
if root is None:
return 0
else:
return max(BST.height(root.left), BST.height(root.right)) + 1
from BinarySearchTree import BST
from TreeNode import TreeNode
tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(9)))
a = BST()
a._subtreeInsert(tree, 10)
a._subtreeInsert(tree, 5)
a._subtreeDelete(tree, 9)
print("PRE-ORDER TRANSVERSE:")
print(a.preOrder(tree))
print("IN-ORDER TRANSVERSE:")
print(a.inOrder(tree))
print("POST-ORDER TRANSVERSE:")
print(a.postOrder(tree))
print("The max depth of the tree is,", a.height(tree),"nodes deep.")
print("There are,", a.treeSize(tree),"nodes in this tree.")
有谁知道我的高度函数不能正常工作的原因吗?谢谢!
你的函数 height
是 class BST
的实例方法,你需要通过 self
调用它而不是 class BST
。
因此,在您的特定情况下,这是:
def height(self, root):
if root is None:
return 0
else:
return max(self.height(root.left), self.height(root.right)) + 1
但是,您的函数 height
实际上并不依赖与搜索树直接关联的任何数据。 self
只需要继续递归。因此,您也可以通过 staticmethod
decorator:
将其转换为 static 方法
@staticmethod
def height(root):
if root is None:
return 0
else:
return max(BST.height(root.left), BST.height(root.right)) + 1
或者,您也可以将函数完全移出 BST
class 并摆脱 BST.height
并通过 height
.[=26 调用它=]
根据您发布的代码,这基本上适用于 BST
class 的所有功能。我真的不认为有必要这样做。你只能在你的 python 模块中使用 TreeNode
和一些顶级函数(没有 BST
class)来修改你的树并与之交互。
在我的二叉搜索树中,我正在制作一个深度函数,它会告诉用户他们插入的树的深度是多少。此功能对于我从最大深度节点删除节点的独特删除功能至关重要。我想我知道问题到底出在哪里,但我不确定。
这是我一直收到的错误。
C:\Python33\python.exe "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py"
Traceback (most recent call last):
PRE-ORDER TRANSVERSE:
File "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py", line 19, in <module>
4
print("The max depth of the tree is,", a.height(tree),"nodes deep.")
2
File "C:\Users\koopt_000\Desktop\College\Sophomore Semester 2\Computer Science 231\Chapter7\BinarySearchTree.py", line 245, in height
1
3
7
6
5
10
None
IN-ORDER TRANSVERSE:
1
2
3
4
5
6
7
10
None
POST-ORDER TRANSVERSE:
1
return max(BST.height(root.left), BST.height(root.right)) + 1
3
TypeError: height() missing 1 required positional argument: 'root'
2
5
6
10
7
4
None
Process finished with exit code 1
现在我认为我的问题出现在这段代码中:
return max(BST.height(root.left), BST.height(root.right)) + 1
我相信这句话是导致它的原因,因为它让我调用 BST 函数,高度函数已经在其中 'work'。我简单地尝试了"height.(root.left)",这没有用,因为它说没有全局变量高度。事实并非如此我不相信。
这是我的函数的完整代码列表,从我的树节点开始,然后是我的 BST 文件(主要),然后是我的测试代码。
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
self.item = data
self.left = left
self.right = right
def __str__(self):
return str(self.item)
from TreeNode import TreeNode
class BST(object):
#------------------------------------------------------------
def __init__(self):
"""create empty binary search tree
post: empty tree created"""
self.root = None
self.size = 0
def delete(self, item):
"""remove item from binary search tree
post: item is removed from the tree"""
self.root = self._subtreeDelete(self.root, item)
#------------------------------------------------------------
def _subtreeDelete(self, root, item):
if root is None: # Empty tree, nothing to do
return None
if item < root.item: # modify left
root.left = self._subtreeDelete(root.left, item)
elif item > root.item: # modify right
root.right = self._subtreeDelete(root.right, item)
else: # delete root
if root.left is None: # promote right subtree
root = root.right
elif root.right is None: # promote left subtree
root = root.left
else:
# root node can't be deleted, overwrite it with max of
# left subtree and delete max node from the subtree
root.item, root.left = self._subtreeDelMax(root.left)
return root
def _subtreeDelMax(self, root):
if root.right is None: # root is the max
return root.item, root.left # return max and promote left subtree
else:
# max is in right subtree, recursively find and delete it
maxVal, root.right = self._subtreeDelMax(root.right)
return maxVal, root
def height(self, root):
if root is None:
return 0
else:
return max(BST.height(root.left), BST.height(root.right)) + 1
from BinarySearchTree import BST
from TreeNode import TreeNode
tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(9)))
a = BST()
a._subtreeInsert(tree, 10)
a._subtreeInsert(tree, 5)
a._subtreeDelete(tree, 9)
print("PRE-ORDER TRANSVERSE:")
print(a.preOrder(tree))
print("IN-ORDER TRANSVERSE:")
print(a.inOrder(tree))
print("POST-ORDER TRANSVERSE:")
print(a.postOrder(tree))
print("The max depth of the tree is,", a.height(tree),"nodes deep.")
print("There are,", a.treeSize(tree),"nodes in this tree.")
有谁知道我的高度函数不能正常工作的原因吗?谢谢!
你的函数 height
是 class BST
的实例方法,你需要通过 self
调用它而不是 class BST
。
因此,在您的特定情况下,这是:
def height(self, root):
if root is None:
return 0
else:
return max(self.height(root.left), self.height(root.right)) + 1
但是,您的函数 height
实际上并不依赖与搜索树直接关联的任何数据。 self
只需要继续递归。因此,您也可以通过 staticmethod
decorator:
@staticmethod
def height(root):
if root is None:
return 0
else:
return max(BST.height(root.left), BST.height(root.right)) + 1
或者,您也可以将函数完全移出 BST
class 并摆脱 BST.height
并通过 height
.[=26 调用它=]
根据您发布的代码,这基本上适用于 BST
class 的所有功能。我真的不认为有必要这样做。你只能在你的 python 模块中使用 TreeNode
和一些顶级函数(没有 BST
class)来修改你的树并与之交互。