python - 二叉搜索树插入功能无法向树中添加新节点

问题描述

我正在编写代码以在 Python 中实现二叉搜索树。我在编写函数时遇到了问题insert，它应该在树中正确的顺序位置添加一个新节点。我用两种不同的方式编写了它：insertNode1工作正常（正确地在树上执行插入），但insertNode2没有正确执行插入。当我使用insertNode1and对树执行 InOrderTraversalinsertNode2时，结果表明“insertNode1”产生了完整的树，而“insertNode2”只产生了根。

为什么它insertNode1成功而insertNode2失败，导致这种情况的两个函数之间的有意义的区别是什么？

这是我的代码：

def insert(self,val):
    if not self.root:
      self.root = TreeNode(val)
    else:
      self.insertNode2(self.root, val)

  def insertNode1(self,node, val):
    if val < node.val:
      if not node.left:
        node.left = TreeNode(val)
      else:
        self.insertNode1(node.left,val)
    else:
      if not node.right:
        node.right = TreeNode(val)
      else:
        self.insertNode1(node.right, val)

  def insertNode2(self, node, val):
    if not node:
      node = TreeNode(val)
    else:
      if node.val > val:
        self.insertNode2(node.left, val)
      else:
        self.insertNode2(node.right, val)

标签： pythoninsertbinary-search-tree

insertNode2由于 line 没有按预期正确执行插入node = TreeNode(val)，这对 . 进行了纯粹的本地分配node。这个新对象永远不会设置为其父对象.left或.right属性，并且在函数返回时丢失。在此函数的任何运行中都不会修改根节点。

要么使用 already-working insertNode1，要么在父函数调用范围内向新子函数添加return node语句insertNode2并进行赋值。

这是一个片段，展示了如何做到这一点：

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinarySearchTree:
    @staticmethod
    def p(root, depth=0):
        if root:
            print(" " * depth + str(root.val))
            BinarySearchTree.p(root.left, depth + 2)
            BinarySearchTree.p(root.right, depth + 2)

    @staticmethod
    def insert(node, val):
        if not node:
            return TreeNode(val)    
        elif node.val > val:
            node.left = BinarySearchTree.insert(node.left, val)
        else:
            node.right = BinarySearchTree.insert(node.right, val)

        return node

if __name__ == "__main__":
    root = TreeNode(5)

    for n in [2, 1, 3, 7, 9, 6]:
        BinarySearchTree.insert(root, n)

    BinarySearchTree.p(root)

输出：

这相当于：

python - 二叉搜索树插入功能无法向树中添加新节点

问题描述

解决方案

推荐阅读