Python 3:二进制搜索树无法设置节点
Python 3:二进制搜索树无法设置节点
提问于 2018-07-26 11:43:24
所以我一直在做这个类项目，实现一个二进制搜索树。教授希望我们使私有递归，而使公共递归简单。(就像when to insert_element(50)一样，它调用一个私有函数recursive_insert(50，self.__root)来求解)。
我的插入函数运行时没有错误，但是测试用例总是返回空的，下面是我的私有函数的代码：
class Binary_Search_Tree:
class __BST_Node:
def __init__(self, value):
self.value = value
self.left=None
self.right=None
def __init__(self):
self.__root = None
self.__height=0
self.__size=0
def _in_order_str(self, root):
if root is None:
outcome= "[ ]"
elif self.__size==1:
outcome = "[ " + str(root.value) + " ]"
else:
outcome = "[ "
self._in_order_str(root.left)
outcome += str(root.value) +", "
self._in_order_str(root.right)
outcome+= " ]"
return outcome
def _recur_ins(self, val,root):
if root is None:
root=Binary_Search_Tree.__BST_Node(val)
elif root.value>val:
root.left = _recur_ins(val,root.left) #do I need self here?
elif root.value <val:
root.right = _recur_ins(val,root.right)
return root这个是为公众准备的：
def insert_element(self, value):
self._recur_ins(value,self.__root)
self.__size+=1 我的测试用例：
def test_insertion_from_empty(self):
root=None
self.__bst.insert_element(50)
self.__bst.insert_element(30)
self.__bst.insert_element(70)
self.assertEqual('[ 30, 50, 70 ]', self.__bst.in_order())更新:我认为问题出在我的_in_order_str(self, root):方法上。我在网上找到的一般案例是：
def inorder(root):
if root is not None:
inorder(root.left)
print root.key
inorder(root.right)我知道这可能是一个非常愚蠢的问题，但我自己真的搞不懂。任何帮助都将不胜感激，非常感谢！
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-07-26 14:42:23
在尽可能少地更改代码之后，我想我已经设法让它正常工作了。
from pprint import pprint # For debugging
class Binary_Search_Tree:
class __BST_Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def __init__(self):
self.__root = None
self.__height = 0
self.__size = 0
def __in_order_str(self, root):
if root is None:
outcome = "[ ]"
elif self.__size == 1:
outcome = "[ " + str(root.value) + " ]"
else:
outcome = "[ "
self.__in_order_str(root.left)
outcome += str(root.value) + ", "
self.__in_order_str(root.right)
outcome += " ]"
return outcome
def __recur_ins(self, val, root):
if root is None:
root = Binary_Search_Tree.__BST_Node(val)
elif root.value > val:
root.left = self.__recur_ins(val, root.left)
elif root.value < val:
root.right = self.__recur_ins(val, root.right)
return root
def insert_element(self, value):
self.__root = self.__recur_ins(value, self.__root)
self.__size += 1
def test_insertion_from_empty(self):
self.insert_element(50)
self.insert_element(60)
self.insert_element(70)
# self.assertEqual('[ 30, 50, 70 ]', self.__bst.in_order())
test = Binary_Search_Tree()
test.test_insertion_from_empty()
pprint(vars(test))有关更改的说明：
- 将一些函数(_recur_ins、_in_order_str)从使用'_‘更改为'__’，以使其成为私有函数。我是基于Python Official Documentation做的，私有函数在insert_element中使用了至少两个前导下划线和最多一个尾随underscore.
- First行，添加了'self.__root=‘，以便返回的根值将被存储为新的根
- 加上'self.’‘。在'__recur_ins‘前面，因为据我所知，每当需要调用位于同一个类中的函数时，都必须使用self。
- 我在__in_order_str中没有做太多修改，因为我认为作者只要求插入__in_order_str assertEqual，因为问题(？)中没有提供函数
- 修改了空格，使其更具可读性
如果我在转储变量之前设置调试模式，我会得到如下结果：
我认为这应该是正确的。首先插入50，因此将其用作根，然后将60插入到50的右子元素上，然后将70放在60的右子元素上。
注意:我也只是个新手，有什么错误请告诉我，我会改正的:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51530678
复制相关文章
相似问题