python - python中的二进制搜索树不起作用

Question

class Node:
    '''represents a new node in the BST'''
    def __init__(self,key):
        self.key=key
        self.disconnect()
    def disconnect(self):
        self.left=None;
        self.right=None;
        self.parent=None;
    def __str__(self):
        return 'node with kay %s'%self.key

class BST:
    def __init__(self):
        self.root=None
    def insert(self,t):
        '''inserts a new element into the tree'''
        self.find_place(self.root,t)

    def find_place(self,node,key):
        """finds the right place of the element recursively"""
        if node is None:
            node=Node(key)
            print node
        else:
            if node.key > key:
                find_place(node.left,key)
            else:
                find_place(node.right,key)
def test():
    '''function to test if the BST is working correctly'''

我写了上面的代码来实现二叉搜索树，但是插入方法没有按预期工作，它甚至无法添加根元素。我无法理解原因。

Answer 1

您实际上并没有向树中添加任何节点!

显式管理根节点的添加是最简单的，正如您在下面的 insert 中看到的那样。

一个 find_place 函数会，大概从名称中，返回父节点以及它是键的左插槽还是右插槽？我在下面创建了一个显式的 _do_insert 函数，它既可以遍历又可以执行插入。

从那时起，您需要遍历这棵树，每次查看您是否递归到一个分支，或者您是否到达了一个空槽，然后在此处添加新节点。

重构您的代码以将遍历树(以及执行添加、删除等)的责任放到 Node 类中可能很自然。

在下面的代码中，我忽略了添加一个已经在树中的键，我只是静静地退出:

def insert(self,t):
    '''inserts a new element into the tree'''
    if self.root is None:
        self.root = Node(t)
    else:
        self._do_insert(self.root,t)

def _do_insert(self,parent,t):
    if t > parent.key:
        if parent.left is None:
            parent.left = Node(t)
        else:
            self._do_insert(parent.left,t)
    elif t < parent.key:
        if parent.right is None:
            parent.right = Node(t)
        else:
            self._do_insert(parent.right,t)
    else:
        # raise a KeyError or something appropriate?
        pass