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

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 

Защиту вставки (самость, VAL): если self._sort_key не None: sort_key = значение // если ни одна из кнопок сортировки, ключ сортировки не является значением еще: sort_key = self._sort_key (вал)

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) 

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