二进制搜索树不会插入/打印实际的最大值，除非它被实现为

Question

我正在学习二叉搜索树，并自己做了一个。我的树的问题是traverse()方法不会打印最大的值（在下面粘贴的代码中为15），除非它是要插入的第一个值。在

我也尝试过getMaxValue()函数，它也不返回期望值，而是给出第二大值。 这使我认为问题一定出在insert()函数的某个地方，但是已经过了一个小时，我找不到解决方法，也找不到我做错了什么。在

class Node(object):

  def __init__(self,data):
    self.data = data
    self.leftChild = None
    self.rightChild = None


class BinarySearchTree(object):

  def __init__(self):
    self.root = None

  #Parent function of insert
  def insert(self,data):
    if not self.root:
      self.root = Node(data)
    else:
      self.insertNode(data,self.root)

  # O(log n) if the tree is balanced!!!! 
  # thats why AVL and RBT are needed!
  #Child function of insert
  def insertNode(self,data,node):

    if data < node.data:
      # check if there is already a left child, if it is not null then we call insertNode recursively and insert a node as its child
      if node.leftChild:
        self.insertNode(data,node.leftChild)
        # if there is no left child then we instantiate it, and make a left child, same stuff happening for right child 
      else:
        node.leftChild = Node(data)
    else:
      if node.rightChild:
        self.insertNode(data, node.rightChild)
      else:
        self.rightChild = Node(data)

#Parent function of getminvalue
  def getMinValue(self):
    if self.root:
      return self.getMin(self.root)

#Child function of getminvalue
  def getMin(self,node):
  #if there is a left child
    if node.leftChild:
      #go to left child recursively
      return self.getMin(node.leftChild)

    return node.data

#Parent function of getMaxValue  
  def getMaxValue(self):
    if self.root:
      return self.getMax(self.root)

#Child function of getmaxValue
  def getMax(self, node):

    if node.rightChild:
      return self.getMax(node.rightChild)

    return node.data 

#Parent function of traverse
  def traverse(self):
    if self.root:
      self.traverseInOrder(self.root)

#Child function of traverseinOrder  
  def traverseInOrder(self,node):

    if node.leftChild:
      self.traverseInOrder(node.leftChild)

    print("%s " % node.data)

    if node.rightChild:
      self.traverseInOrder(node.rightChild)


#Inputs
bst = BinarySearchTree()

bst.insert(10)
bst.insert(15)
bst.insert(5)
bst.insert(4)
bst.insert(3)

print(bst.traverse())

预期结果是

^{pr2}$

但我得到了

3
4
5
10 
None

Answer 1

固定的：

将很快编辑详细信息

class Node(object):

  def __init__(self,data):
    self.data = data
    self.leftChild = None
    self.rightChild = None


class BinarySearchTree(object):

  def __init__(self):
    self.root = None

  #Parent function of insert
  def insert(self,data):
    if not self.root:
      self.root = Node(data)
    else:
      self.insertNode(data,self.root)

  # O(log n) if the tree is balanced!!!!
  # thats why AVL and RBT are needed!
  #Child function of insert
  def insertNode(self,data,node):

    if data < node.data:
      # check if there is already a left child, if it is not null then we call insertNode recursively and insert a node as its child
      if node.leftChild:
        self.insertNode(data,node.leftChild)
        # if there is no left child then we instantiate it, and make a left child, same stuff happening for right child
      else:
        node.leftChild = Node(data)
    else:
      if node.rightChild:
        self.insertNode(data, node.rightChild)
      else:
        node.rightChild = Node(data)

#Parent function of getminvalue
  def getMinValue(self):
    if self.root:
      return self.getMin(self.root)

#Child function of getminvalue
  def getMin(self,node):
  #if there is a left child
    if node.leftChild:
      #go to left child recursively
      return self.getMin(node.leftChild)

    return node.data

#Parent function of getMaxValue
  def getMaxValue(self):
    if self.root:
      return self.getMax(self.root)

#Child function of getmaxValue
  def getMax(self, node):

    if node.rightChild:
      return self.getMax(node.rightChild)

    return node.data

#Parent function of traverse
  def traverse(self):
    if self.root:
      self.traverseInOrder(self.root)

#Child function of traverseinOrder
  def traverseInOrder(self,node):

    if node.leftChild:
      self.traverseInOrder(node.leftChild)

    print("%s " % node.data)

    if node.rightChild:
      self.traverseInOrder(node.rightChild)


#Inputs
bst = BinarySearchTree()

bst.insert(10)
bst.insert(15)
bst.insert(5)
bst.insert(4)
bst.insert(3)

bst.traverse()

我使用调试器逐步完成了代码（我建议您这样做，这非常有帮助），并看到了以下内容：

{a1}

如您所见，带有数据10的node没有正确的子代，而self有一个root，数据为10，而{}包含数据15。在

这让我看到了插入一个新的右子元素的行，你错写了：self.rightChild = Node(data)而不是{}（就像你正确处理左子元素一样）