Binary Search Tree in python che non funziona

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'''

ho scritto il codice qui sopra per implementare un albero binario di ricerca, ma il metodo di inserimento non funziona come previsto, non riesce a aggiungere ancora l'elemento principale. non riesco a capirne la causa.

Answer 1

Si sta in realtà non aggiungere alcun nodi per l'albero!

La sua più semplice per gestire l'aggiunta del nodo principale in modo esplicito, come vedete ho fatto seguito nella insert.

Una funzione find_place sarebbe, presumibilmente dal nome, restituire il nodo padre ed anche se è la fessura a destra oa sinistra per la chiave? Ho fatto una funzione _do_insert esplicita di sotto di tale sia cammina e fa l'inserto.

Da allora in poi, è necessario camminare l'albero, ogni volta vedere se si ricorsione giù un ramo o se hai raggiunto uno slot vuoto, in cui si aggiunge il nuovo nodo.

Potrebbe essere naturale di refactoring il codice per mettere la responsabilità per camminare l'albero (e facendo aggiunge, rimuove e come) nella classe Node.

Nel codice qui sotto, ignoro l'aggiunta di una chiave che è già nell'albero, esco solo silenzio:

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

Ecco un altro BST con Python, utilizzando una chiave di ordinamento

A SINISTRA = 0 RIGHT = 1 VALUE = 2 SORT_KEY = -1

class BinarySearchTree (oggetto):

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

def inserire (self, val):     se self._sort_key è None:         sort_key = val // se no chiave di ordinamento, chiave di ordinamento è un valore     altro:         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)

chiave Ordina è sostituito dal valore se qualsiasi.