如何在Python中实现二叉搜索树？

Question

这是我迄今为止得到的内容，但它没有起作用：

class Node:
    rChild,lChild,data = None,None,None

    def __init__(self,key):
        self.rChild = None
        self.lChild = None
        self.data = key

class Tree:
    root,size = None,0
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self,node,someNumber):
        if node is None:
            node = Node(someNumber)
        else:
            if node.data > someNumber:
                self.insert(node.rchild,someNumber)
            else:
                self.insert(node.rchild, someNumber)
        return

def main():
    t = Tree()
    t.root = Node(4)
    t.root.rchild = Node(5)
    print t.root.data #this works
    print t.root.rchild.data #this works too
    t = Tree()
    t.insert(t.root,4)
    t.insert(t.root,5)
    print t.root.data #this fails
    print t.root.rchild.data #this fails too

if __name__ == '__main__':
     main()

- chochim

---

paste the error messages too. - N 1.1

@Rohit，“我感兴趣的不是实现，而是为什么我的代码不起作用。”但是你的代码不起作用是因为你的实现不正确。在你的主函数中使用“search”没有太多意义。作为一种友好的建议，也许你可以先编写一个简单的树创建程序，然后对其进行一些前序和后序遍历。谢谢。 - eat

@Lennart，@N 1.1 - 对不起。问题出在二叉搜索树的插入上。如果你看一下主函数，前五行按预期工作，但接下来的五行却没有。 @kriegar - 谢谢你提到这个 :) @eat - 我想我找到了我的错误。感谢你指出这一点。 - chochim

@Rohit 我想指出，在插入方法中，if和else的语句是相同的，如果你决定修改而不是重写你的代码，请确保仔细查看它。 - dting

现有的平衡二叉搜索树实现：https://dev59.com/aHNA5IYBdhLWcg3wC5Xh - Ciro Santilli OurBigBook.com

Answer 1

以下是二分插入的一个快速示例：

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def binary_insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                binary_insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                binary_insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)    

---

r = Node(3)
binary_insert(r, Node(7))
binary_insert(r, Node(1))
binary_insert(r, Node(5))

---

     3
    / \
   1   7
      /
     5

---

print "in order:"
in_order_print(r)

print "pre order"
pre_order_print(r)

in order:
1
3
5
7
pre order
3
1
7
5

- dting

---

非常感谢您。谢谢。显然，当我看到这个时候，我已经能够实现自己的版本了。尽管您的版本代码行数更少（我的包含一些冗余）。 - chochim

如果根节点的数据与当前节点的数据相同，难道不应该采取更好的措施而不是插入重复的节点吗？他已经在实现一个不平衡的树结构；往里面塞入重复的节点并不能提高性能。 - John Machin

不需要进行 root.l_child == None 和 root.r_child == None 检查。binary_insert 调用会处理它。 - ealeon

@ealeon，不行的：如果您删除这些检查，该代码将无法将任何新节点附加到树中。无用的部分是 if root is None: root = None。此代码的另一个问题是它允许重复项。可以通过将 else 更改为 elif root.data < node.data 来解决这个问题。 - laurids

这个实现忽略了为每个“节点”设置“parent”属性，没有这个属性就无法实现“successor”方法来查找中序遍历中下一个节点的时间复杂度为_O_(h)（其中_h_是树的高度），而不是中序遍历的_O_(n)时间复杂度。请参见下面的答案，其中包含具有这些功能的BST。 - Kurt Peek

Answer 2

class Node: 
    rChild,lChild,data = None,None,None

这是错误的 - 它会使您的变量成为 类变量 - 也就是说，每个 Node 实例都使用相同的值（更改任何节点的 rChild 将更改所有节点的 rChild！）。这显然不是您想要的；请尝试：

class Node: 
    def __init__(self, key):
        self.rChild = None
        self.lChild = None
        self.data = key

现在每个节点都有自己的变量集。对于您对树的定义也是如此。

class Tree:
    root,size = None,0    # <- lose this line!
    def __init__(self):
        self.root = None
        self.size = 0

此外，每个类都应该是从“object”类派生的“新式”类，并且应该链接回object.__init__():

class Node(object): 
    def __init__(self, data, rChild=None, lChild=None):
        super(Node,self).__init__()
        self.data   = data
        self.rChild = rChild
        self.lChild = lChild

class Tree(object):
    def __init__(self):
        super(Tree,self).__init__()
        self.root = None
        self.size = 0

此外，main()缩进太多了 - 如所示，它是Tree的一个方法，因为它不接受self参数而无法调用。

此外，您正在直接修改对象的数据（t.root = Node(4)），这种操作会破坏封装性（首先使用类的整个目的）; 您应该做一些更像这样的事情

def main():
    t = Tree()
    t.add(4)    # <- let the tree create a data Node and insert it
    t.add(5)

- Hugh Bothwell

---

“更改任何节点的rChild会更改所有节点！”是无意义的。它会创建一个实例属性。请参见我的编辑答案。 - John Machin

@John Machin：谢谢您指出这一点；即使Node.xyz已经存在，self.xyz也会引用实例变量。无论如何，具有与实例变量相同名称的未使用类变量是不必要和令人困惑的，最好不要这样做。 - Hugh Bothwell

@John Machin：天空将会坍塌，海洋将会燃烧，而你可能会培养出一种机智的感觉。在这种情况下，省略super()几乎没有什么影响；但是如果以后有人开发了一个从Tree多重继承的子类，那么这将会给他们带来麻烦。最好从一开始就做对。 - Hugh Bothwell

@Hugh Bothwell - 我在下面展示了我的代码版本。我已经包含了你要求我省略的那些行。但是显然，代码似乎可以工作。还是谢谢你的分享。遵循最佳实践总是好的 - 今天学到了新东西。 - chochim

@Rohit：Hugh要求你省略的那些行是浪费空间的；它们的效果被__init __()调用覆盖了。 - John Machin

Answer 3

class Node:
    rChild,lChild,parent,data = None,None,None,0    

def __init__(self,key):
    self.rChild = None
    self.lChild = None
    self.parent = None
    self.data = key 

class Tree:
    root,size = None,0
    def __init__(self):
        self.root = None
        self.size = 0
    def insert(self,someNumber):
        self.size = self.size+1
        if self.root is None:
            self.root = Node(someNumber)
        else:
            self.insertWithNode(self.root, someNumber)    

    def insertWithNode(self,node,someNumber):
        if node.lChild is None and node.rChild is None:#external node
            if someNumber > node.data:
                newNode = Node(someNumber)
                node.rChild = newNode
                newNode.parent = node
            else:
                newNode = Node(someNumber)
                node.lChild = newNode
                newNode.parent = node
        else: #not external
            if someNumber > node.data:
                if node.rChild is not None:
                    self.insertWithNode(node.rChild, someNumber)
                else: #if empty node
                    newNode = Node(someNumber)
                    node.rChild = newNode
                    newNode.parent = node 
            else:
                if node.lChild is not None:
                    self.insertWithNode(node.lChild, someNumber)
                else:
                    newNode = Node(someNumber)
                    node.lChild = newNode
                    newNode.parent = node                    

    def printTree(self,someNode):
        if someNode is None:
            pass
        else:
            self.printTree(someNode.lChild)
            print someNode.data
            self.printTree(someNode.rChild)

def main():  
    t = Tree()
    t.insert(5)  
    t.insert(3)
    t.insert(7)
    t.insert(4)
    t.insert(2)
    t.insert(1)
    t.insert(6)
    t.printTree(t.root)

if __name__ == '__main__':
    main()

我的解决方案。

- chochim

Answer 4

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

    def __str__(self):
        return "[%s, %s, %s]" % (self.left, str(self.val), self.right)

    def isEmpty(self):
        return self.left == self.right == self.val == None

    def insert(self, val):
        if self.isEmpty():
            self.val = val
        elif val < self.val:
            if self.left is None:
                self.left = BST(val)
            else:
                self.left.insert(val)
        else:
            if self.right is None:
                self.right = BST(val)
            else:
                self.right.insert(val)

a = BST(1)
a.insert(2)
a.insert(3)
a.insert(0)
print a

- Aram Kocharyan

---

我发现使用__str __()返回以下内容更容易阅读："%s: [%s, %s]" % (str(self.val), self.left, self.right) - Daryl Spitzer

Answer 5

Op的Tree.insert方法有望获得“本周最大的错误命名”奖项--它并没有插入任何东西。它创建了一个未连接到任何其他节点的节点（并没有任何节点可以连接它），然后在方法返回时，该节点被丢弃。

为了让@Hugh Bothwell受益:

>>> class Foo(object):
...    bar = None
...
>>> a = Foo()
>>> b = Foo()
>>> a.bar
>>> a.bar = 42
>>> b.bar
>>> b.bar = 666
>>> a.bar
42
>>> b.bar
666
>>>

- John Machin

---

@Rohit：这个答案对于你解决问题有所帮助吗？现在可以分享一下你的BST实现吗？谢谢。 - eat

@eat - @John Machin 提供的代码片段对我没有帮助。但他说的我的代码没有连接任何节点是正确的。用笔和纸来操作有所帮助。我已经在最后附上了我的实现。 - chochim

@Rohit：我没有给你提供任何“代码片段”。正如我所指出的那样，这次编辑是针对@Hugh Bothwell进行的。 - John Machin

Answer 6

被接受的答案忽略了为每个插入的节点设置父属性，没有这个属性就无法实现一个 successor 方法，该方法可以在中序树遍历中以 O(h) 的时间复杂度找到后继节点，其中 h 是树的高度（与需要遍历的 n 个节点的 O(n) 时间复杂度相对应）。

以下是基于 Cormen 等人所提供的伪代码实现，包括分配一个 parent 属性和一个 successor 方法的内容：

class Node(object):
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None


class Tree(object):
    def __init__(self, root=None):
        self.root = root

    def insert(self, z):
        y = None
        x = self.root
        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y is None:
            self.root = z       # Tree was empty
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    @staticmethod
    def minimum(x):
        while x.left is not None:
            x = x.left
        return x

    @staticmethod
    def successor(x):
        if x.right is not None:
            return Tree.minimum(x.right)
        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y

以下是一些测试，展示了树对DTing提供的示例的预期表现：

import pytest

@pytest.fixture
def tree():
    t = Tree()
    t.insert(Node(3))
    t.insert(Node(1))
    t.insert(Node(7))
    t.insert(Node(5))
    return t

def test_tree_insert(tree):
    assert tree.root.key == 3
    assert tree.root.left.key == 1
    assert tree.root.right.key == 7
    assert tree.root.right.left.key == 5

def test_tree_successor(tree):
    assert Tree.successor(tree.root.left).key == 3
    assert Tree.successor(tree.root.right.left).key == 7

if __name__ == "__main__":
    pytest.main([__file__])

- Kurt Peek

---

谢谢 - 如果变量名比x y z更有意义，那么更容易理解代码。我猜这是我们的作业 :) - Jean Monet

Answer 7

以下是一些帮助你入门的内容。

二叉树搜索（简单的想法）很可能会按照以下方式在Python中实现：

def search(node, key):
    if node is None: return None  # key not found
    if key< node.key: return search(node.left, key)
    elif key> node.key: return search(node.right, key)
    else: return node.value  # found key

现在你只需要实现脚手架（树的创建和值的插入），然后就完成了。

- eat

---

谢谢您发布这篇文章。但这不是我要找的内容。我的问题出在插入方面，现在已经解决了（我的解决方案如下）。问题更多地与我对Python类的理解有关。 - chochim

Answer 8

使用两个类很容易实现BST，即1.节点类和2.树类。 树类仅用于用户界面，实际方法将在节点类中实现。

class Node():

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


    def _insert(self,data):
        if data == self.value:
            return False
        elif data < self.value:
            if self.left:
                return self.left._insert(data)
            else:
                self.left = Node(data)
                return True
        else:
            if self.right:
                return self.right._insert(data)
            else:
                self.right = Node(data)
                return True

    def _inorder(self):
        if self:
            if self.left:
                self.left._inorder()
            print(self.value)
            if self.right:
                self.right._inorder()



class Tree():

    def __init__(self):
        self.root = None

    def insert(self,data):
        if self.root:
            return self.root._insert(data)
        else:
            self.root = Node(data)
            return True
    def inorder(self):
        if self.root is not None:
            return self.root._inorder()
        else:
            return False




if __name__=="__main__":
    a = Tree()
    a.insert(16)
    a.insert(8)
    a.insert(24)
    a.insert(6)
    a.insert(12)
    a.insert(19)
    a.insert(29)
    a.inorder()

检查二叉搜索树是否正确实现的中序函数。

- nirav bharadiya

Answer 9

我觉得在插入部分的解决方案有些笨重。你可以返回root引用并将其简化一些：

def binary_insert(root, node):
    if root is None:
        return node
    if root.data > node.data:
        root.l_child = binary_insert(root.l_child, node)
    else:
        root.r_child = binary_insert(root.r_child, node)
    return root

- jlhonora

Answer 10

另一个带排序键（默认为值）的Python二叉搜索树

LEFT = 0
RIGHT = 1
VALUE = 2
SORT_KEY = -1

class BinarySearchTree(object):

    def __init__(self, sort_key=None):
        self._root = []  
        self._sort_key = sort_key
        self._len = 0  

def insert(self, val):
    if self._sort_key is None:
        sort_key = val // if no sort key, sort key is value
    else:
        sort_key = self._sort_key(val)

    node = self._root
    while node:
        if sort_key < node[_SORT_KEY]:
            node = node[LEFT]
        else:
            node = node[RIGHT]

    if sort_key is val:
        node[:] = [[], [], val]
    else:
        node[:] = [[], [], val, sort_key]
    self._len += 1

def minimum(self):
    return self._extreme_node(LEFT)[VALUE]

def maximum(self):
    return self._extreme_node(RIGHT)[VALUE]

def find(self, sort_key):
    return self._find(sort_key)[VALUE]

def _extreme_node(self, side):
    if not self._root:
        raise IndexError('Empty')
    node = self._root
    while node[side]:
        node = node[side]
    return node

def _find(self, sort_key):
    node = self._root
    while node:
        node_key = node[SORT_KEY]
        if sort_key < node_key:
            node = node[LEFT]
        elif sort_key > node_key:
            node = node[RIGHT]
        else:
            return node
    raise KeyError("%r not found" % sort_key)

- kiriloff