二进制的方法为空

Question

我在python中实现了一个二叉树，并想看看它是否能与isEmpty函数一起工作。当我测试代码并插入一些我没有提到的值时，python以某种方式从树中删除了值，因为如果我检查根是否等于None，我就会得到True。我做错什么了？下面是我的代码：

class BinTree():

    def __init__(self, item = None):

        self.item = item
        self.left = None
        self.right = None

class Tree():

    def __init__(self):

        self.root = None

    def put(self, indata):

        p = self.root
        tree = BinTree(indata)

        if p == None:
            print("yey")
            p = tree
            return p
        else:
            while True:

                if indata > p.item:
                    #if bigger, go right
                    if p.right == None:
                        #if right slot is empty, make one
                        p.right = p
                        return
                        #return to go back to the base level
                    elif p.right != None:
                        #if right slot is full, go deeper
                        p = p.right
                        #do not return to keep same level and repeat the loop
                elif indata < p.item:
                    #if smaller, go left
                    if p.left == None:
                        #if left slot is empty, make one
                        p.left = p
                        return
                        #return to go back to the base level
                    elif p.left != None:
                        #if left slot is full, go deeper
                        p = p.left
                        #do not return to keep same level and repeat the loop
                else:
                    #if equal
                    return False
                    #return False if the value already exist in the tree

    def isempty(self):

        if self.root == None:
            return True
        else:
            print("yey2")
            return False

然后我写在shell中的值：

^{pr2}$

Answer 1

你从不设置self.root；你只设置了反弹。p是一个单独的变量，设置它不会设置self.root。在

如果没有self.root设置，树将保持为空。在

注意，因为None是一个单例，所以在Python中，通常使用is来测试对象。您在put()方法中还犯了其他几个错误，比如用p.right = p创建循环引用，而不是插入新的tree节点。在

我选择了一些不同的变量名，以便更清楚地说明发生了什么；newnode而不是{}和{}，而不是{}：

def put(self, indata):
    newnode = BinTree(indata)

    if self.root is None:
        self.root = newnode
        return self.root

    current = self.root
    while True:
        if indata > current.item:
            # if bigger, go right
            if current.right is None:
                # if right slot is empty, make one
                current.right = newnode
                return newnode
            else:
                current = current.right
        elif indata < current.item:
            # if smaller, go left
            if current.left is None:
                # if left slot is empty, make one
                current.left = newnode
                return newnode
            else:
                # if left slot is full, go deeper
                current = current.left
        else:
            # if equal
            return False

如果节点已经存在于树中，我可能会返回None，而不是{}；这样可以更好地测试条件：

^{pr2}$

您的isempty方法在其他方面是正确的；但是它可以被简化，因为==和{}运算符已经产生{}或{}；只需返回结果：

def isempty(self):
    return self.root is None

有了这些变化，isempty()方法对我很有用：

>>> class BinTree():
...     def __init__(self, item = None):
...         self.item = item
...         self.left = None
...         self.right = None
... 
>>> class Tree():
...     def __init__(self):
...         self.root = None
...     def put(self, indata):
...         newnode = BinTree(indata)
...         if self.root is None:
...             self.root = newnode
...             return self.root
...         current = self.root
...         while True:
...             if indata > current.item:
...                 # if bigger, go right
...                 if current.right is None:
...                     # if right slot is empty, make one
...                     current.right = newnode
...                     return newnode
...                 else:
...                     current = current.right
...             elif indata < current.item:
...                 # if smaller, go left
...                 if current.left is None:
...                     # if left slot is empty, make one
...                     current.left = newnode
...                     return newnode
...                 else:
...                     # if left slot is full, go deeper
...                     current = current.left
...             else:
...                 # if equal
...                 return False
...     def isempty(self):
...         return self.root is None
... 
>>> tree = Tree()
>>> tree.isempty()
True
>>> tree.put(5)
<__main__.BinTree object at 0x10a520cf8>
>>> tree.isempty()
False