二叉树的方法 isEmpty

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 中写入的值：

>>> Tree().put(9)
yey
<__main__.BinTree object at 0x105a57eb8>
>>> Tree().isempty()
True

Answer 1

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

没有 self.root 设置，你的树仍然是空的。

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

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

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

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

newnode = tree.put(datapoint)
if newnode is None:
    # already present in the tree, do something with that info

您的 isempty 方法在其他方面是正确的；它可以被简化，因为 == 和 is 运算符已经产生 True 或 False；只是 return 结果：

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

二叉树的方法 isEmpty

Method isEmpty for binary tree

python

binary-tree

python-3.x