Python3：二叉搜索树设置节点失败

Question

所以我一直致力于这个 class 项目，该项目实现了一个二叉搜索树。教授希望我们使 private 递归，同时使 public 简单。（比如到insert_element(50)的时候，调用了一个私有函数recursive_insert(50, self.__root)来求解）

我的插入函数运行没有错误，但测试用例总是return空，这里是我的私有函数代码：

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

而这个是给 public:

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)

我知道这可能是一个非常愚蠢的问题，但我真的没办法自己想出来。任何帮助将不胜感激，非常感谢！！！

Answer 1

尽可能少地更改您的代码后，我想我已经设法让它工作了。

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的第一行，添加了'self.__root= '以便返回的根值将被存储为新的根
在'__recur_ins'前面添加了'self.'，因为据我所知，当你需要调用位于相同[=50的函数时，你必须使用self =].
我没有对__in_order_str做太多修改，因为我认为作者只是要求插入(?)
评论了assertEqual，因为问题中没有提供函数(?)
修改了空格，使其更具可读性

如果我在转储变量之前设置调试模式，这就是我得到的：

我认为应该是正确的。先插入50，因此作为根，然后在50的右边child插入60，在60的child右边插入70.

注：我也是新手，有什么错误请告诉我，我会改正:)

Python3：二叉搜索树设置节点失败

Python 3: Binary Search Tree failed to set nodes

python

binary-tree

binary-search-tree

python-3.x