Двоичное дерево поиска в Python не работает - PullRequest
Новая
       2

Двоичное дерево поиска в Python не работает

2 голосов
/ 20 июня 2010 
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'''

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

Ответы [ 2 ]

2 голосов
/ 20 июня 2010

Вы на самом деле не добавляете какие-либо узлы в дерево!

Проще всего управлять добавлением корневого узла в явном виде, как вы видите ниже в 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
0 голосов
/ 29 апреля 2013

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

LEFT = 0 ПРАВО = 1 VALUE = 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 - None: sort_key = val // если ключа сортировки нет, ключом сортировки является значение еще: 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)

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

...