Двоичное дерево поиска в 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'''

Я написал вышеуказанный код для реализации двоичного дерева поиска, но метод INSERT не работает должным образом, он не выполняет даже корневой элемент. Я не могу предал причину.

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

Answer 2

Вот еще одна BST с Python, используя ключ сортировки

Левое = 0 справа = 1 значение = 2 sort_key = -1

Класс BinarySearchtree (объект):

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

def insert (self, val): если self._sort_key нет: sort_key = val // Если нет ключа сортировки, клавиша сортировки - это значение 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)

Ключ сортировки заменен значением, если таковые имеются.