我正在尝试在 python 中实现二叉搜索树，插入方法没有按预期工作，正确的节点元素没有插入到树中？

Question

enter code here

class Node:
    def __init__(self,data=None):
        self.data = data
        self.left = None
        self.right = None


class binary_tree:

    def __init__(self):
        self.root = None


    def insert(self,data):
        if self.root is None:
            self.root = Node(data)
        else:
            cur_node = self.root
            while cur_node !=None :
                if data < cur_node.data:
                    if cur_node.left is None:
                        cur_node.left = Node(data)
                        print(cur_node.left.data)
                    else:
                        cur_node = cur_node.left
                elif data > cur_node.data:
                    if cur_node.right is None:
                        cur_node.right = Node(data)
                        print(cur_node.right.data)
                    else:
                        cur_node = cur_node.right
                else:
                    print("value already exist")


binary = binary_tree()
b = binary.insert(5)
e = binary.insert(4)
h = binary.insert(7)
print(h)

问。二叉搜索树实现，插入方法没有按预期工作，将节点插入右侧出现错误？如何消除此代码错误？二叉搜索树实现。

Answer 1

代码的问题在于它卡在了 while 循环中。注意条件cur_node != None将永远不会为真。这可以很容易地从以下推导出来：

初始条件（在 while 循环至少执行一次之前）始终是 true，因为只有当 self.root 不是 None.[=47 时我们才能到达此分支=]
在 while 循环体中，我们总是将非 None 值赋给 cur_node。 cur_node = cur_node.left 当 cur_node.left 不是 None 和 cur_node = cur_node.right 当 cur_node.right 不是 None.

因此我们需要以某种方式摆脱循环。可能的修复方法之一是将 while 循环的条件更改为 True 以更好地表达我们的意图，并将循环中的 break （或 return）更改为一旦我们找到插入项目的位置：

cur_node = self.root
while True :
  if data < cur_node.data:
    if cur_node.left is None:
      cur_node.left = Node(data)
      return # break is also possible
   else:
      cur_node = cur_node.left
  elif data > cur_node.data:
    if cur_node.right is None:
      cur_node.right = Node(data)
      return # break is also possible
    else:
      cur_node = cur_node.right

我还注意到，在您的测试中，您编写的代码类似于插入 returns 之类的东西，但实际上并没有，因此 insert 应该这样调用

binary.insert(5)
binary.insert(4)
binary.insert(7)

print(binary.root.data) # 5
print(binary.root.left.data) # 4
print(binary.root.right.data) # 7

如果你想要insert到return的东西，你首先需要定义它应该return（例如插入的节点）然后适当地改变代码。

我正在尝试在 python 中实现二叉搜索树，插入方法没有按预期工作，正确的节点元素没有插入到树中？

i am trying to implement binary search treee in python , insert method not working as expected , right node element are not inserted in tree?

python

data-structures

binary-search-tree

python-3.6