时间戳

首页 > 解决方案 > 为什么在编写二叉搜索树时会出错？

python - 为什么在编写二叉搜索树时会出错？

问题描述

我试图编写一个二叉搜索树，但我遇到了一个错误，说 int 对象没有属性值。这意味着 cur_node 被认为是一个 int 对象。我似乎无法弄清楚为什么。
这是在学习从 youtube 编写二叉搜索树时遇到的。PS：我是 Python 新手，所以如果它很傻，请多多包涵。

class node:
    def __init__(self,value=None):
        self.value=value
        self.left_child=None
        self.right_child=None

class binary_search_tree:
    def __init__(self):
        self.root=None

    def insert(self,value):
        if self.root==None:
            self.root=value
        else:
            self._insert(value,self.root)

    def _insert(self,value,cur_node):
        if value<cur_node.value:
            if cur_node.left_child==None:
                cur_node.left_child=node(value)
            else:
                self._insert(value,cur_node.left_child)
        elif value>cur_node.value:
            if cur_node.right_child==None:
                cur_node.right_child=node(value)
            else:
                self._insert(value,cur_node.right_child)
        else:
            print("Value already in tree")

    def print_tree(self):
        if self.root!=None:
            self._print_tree(self.root)

    def _print_tree(self,cur_node):
        self._print_tree(cur_node.left_child)
        print(str(cur_node.value))
        self._print_tree(cur_node.right_child)

    def height(self):
        if self.root!=None:
            self._height(self.root,0)
        else:
            return 0

    def _height(self,cur_node,cur_height):
        if cur_node==None:
            return cur_height
        left=_height(cur_node.left_child,cur_height)
        right=_height(cur_node.right_child,cur_height)
        return max(left,right)

    def search(self,value):
        if(self.root!=None):
            self._search(self.root,value)
        else:
            return 0

    def _search(self,cur_node,value):
        if(cur_node.value==value):
            return 1
        elif value<cur_node.value and cur_node.left_child!=None:
            return self._search(cur_node.left_child,value)
        elif value>cur_node and cur_node.rightchild!=None:
            return self._search(cur_node.right_child,value)
        return 0

tree=binary_search_tree()
tree.insert(6)
tree.insert(8)
tree.insert(3)
tree.insert(17)
tree.insert(1)
tree.insert(4)

tree.print_tree()

tree.height()

tree.search(5)
tree.search(6)

错误签名是：

Traceback（最近一次调用最后一次）：文件“/Users/suprateem/PycharmProjects/TreeOfLIfe/TreeOfLife.py”，第 70 行，在

tree.insert(8)

文件“/Users/suprateem/PycharmProjects/TreeOfLIfe/TreeOfLife.py”，第 15 行，插入

self._insert(value,self.root)

_insert 中的文件“/Users/suprateem/PycharmProjects/TreeOfLIfe/TreeOfLife.py”，第 18 行

if value<cur_node.value:

AttributeError：“int”对象没有属性“值”

标签： pythonpython-3.xbinary-treebinary-search-tree

解决方案

首先，if x!=None用if x和if x==None替换if not x。x!=None/x==None不是pythonic。如果您确实需要检查None（在您的情况下不需要），您应该使用x is None.

错误在您的插入方法中。您不是node为根创建对象，而是为其分配值。通过以下方式更改它：

def insert(self,value):
    if not self.root:
        self.root=node(value)
    else:
        self._insert(value,self.root)

您在打印方法中也有错误（您应该检查左/右子树是否不是无）：

def _print_tree(self,cur_node):
    if cur_node.left_child: self._print_tree(cur_node.left_child)
    print(str(cur_node.value))
    if cur_node.right_child: self._print_tree(cur_node.right_child)

推荐阅读