Binary Search Baum in Python nicht funktioniert

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

i den obigen Code schrieb einen binären Suchbaum zu implementieren, aber der Einsatz Methode wird nicht wie erwartet funktioniert, scheitert es auch das Root-Element hinzuzufügen. Ich kann nicht undestand die Ursache.

Answer 1

Sie sind nicht wirklich das Hinzufügen alle Knoten auf dem Baum!

Die einfachste ausdrücklich die Zugabe des Root-Knotens zu verwalten, wie Sie sehen, ich habe in dem unten stehenden insert.

Eine find_place Funktion würde, vermutlich aus dem Namen, geben Sie den übergeordneten Knoten und auch, ob es links oder rechts Schlitz für den Schlüssel ist? Ich habe eine explizite _do_insert Funktion unten gemacht, dass beide Wege und macht den Einsatz.

Von nun an müssen Sie den Baum gehen, jedes Mal zu sehen, wenn Sie einen Zweig Rekursion oder ob Sie einen leeren Platz erreicht haben, in dem Sie den neuen Knoten hinzuzufügen.

Es könnte natürlich sein, Ihren Code Refactoring Verantwortung zu setzen, um den Baum zu Fuß (und tun fügt hinzu, entfernt und so weiter) in die Node Klasse.

In dem folgenden Code, ich ignoriere das Hinzufügen einen Schlüssel, der bereits in dem Baum ist, dass ich nur leise Ausgang:

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

Hier ist ein weiteres BST mit Python, eine Sortierschlüssel

Links = 0 RIGHT = 1 VALUE = 2 Sort_key = -1

Klasse BinarySearchTree (Objekt):

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

einfügen def (self, val):     wenn self._sort_key ist None:         sort_key = val // wenn keine Sortierschlüssel, Sortierschlüssel Wert     sonst:         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)

Sortierschlüssel von Wert, wenn ein ersetzt wird.