Binary Search Baum rekursive Implementierung in Python

Question

Ich versuche, binäre Suchbaum in Python mit Rekursion zu implementieren. Ich bin in einigen unendlichen Rekursionen gefangen, die in meinem Programm geschehen. Ich mache rekursive Aufrufe an die Funktion RecursBST, indem ich die Adresse und die Daten übergebe, bis die obere Grenze auf None-Wert des linken oder rechten Kindes abfällt.

class createnode: 
    def __init__(self,data): 
     self.root=data 
     self.left=None 
     self.right=None 

class createbinarysearchtree: 
    def __init__(self, data = None): 
     self.top=None 

    def RecursBST(self,top,data):    
     if self.top is None: 
      self.top=createnode(data)     
     elif self.top.root>data: 
      self.top.left=self.RecursBST(self.top.left,data) 
     elif self.top.root<data: 
      self.top.right=self.RecursBST(self.top.right,data) 

conv=createbinarysearchtree(); 
conv.RecursBST(conv.top,50) 
conv.RecursBST(conv.top,40) 

Ich lief zum unten Fehler:

self.top.left=self.RecursBST(self.top.left,data) 
RuntimeError: maximum recursion depth exceeded 

Answer 1

ich Ihre Klassen Refactoring haben, so dass ihre Namen Sinn machen (Node und BST).

Ich denke, der Hauptfehler in Ihrem Code ist, immer "selbst" zu referenzieren und immer von der selben Instanz zu rufen. Wenn Sie dies tun, erhalten Sie immer die gleichen Daten auf dem Knoten, deshalb endet Ihre Rekursion nie, weil sie immer auf dem gleichen Knoten hängt. Ich denke, es ist einfacher, die Node-Referenz als Parameter zu übergeben, und von dort aus die richtigen rekursiven Aufrufe zu machen, auch, Sie die linken und rechten Variablen zuweisen, aber nie etwas zurückgeben. Überprüfen Sie den Code:

class Node(object): 
    def __init__(self, data): 
     self.root = data 
     self.left = None 
     self.right = None 

class BST(object): 
    def __init__(self): 
     self.top = None 

    def recursBST(self, node, data):    
     if node is None: 
      node = Node(data)     
     elif self.top.root > data: 
      node.left = self.recursBST(node.left, data) 
     elif self.top.root < data: 
      node.right = self.recursBST(node.right, data) 

     return node 

    def insert(self, data): 
     self.top = self.recursBST(self.top, data) 

conv = BST() 
conv.insert(8) 
conv.insert(3) 
conv.insert(6) 
conv.insert(1) 
conv.insert(-1) 
conv.insert(10) 
conv.insert(14) 
conv.insert(50) 

Denken Sie auch daran, das 'Objekt' in einer Python-Klasse hinzuzufügen. Es ist ein Feature, das auf Python 2.7 eingeführt wurde, daher ist es eine schlechte Übung, es nicht einzubinden. Weitere Informationen finden Sie unter this.

Bonus: Sie können überprüfen, ob Ihre Einfügealgorithmen korrekt sind, indem Sie eine In-Order-Transversale durchführen, danach sollten die Elemente in aufsteigender Reihenfolge gedruckt werden (in diesem Fall). Aber das liegt an dir :)

Answer 2

Ihr Code fehlt eine Rekursion Abbruchbedingung zu schaffen, und den Zustand der Rekursion zu ändern:

Von https://en.wikipedia.org/wiki/Recursion_termination

In der Computerverarbeitung wird die Rekursion beendet, wenn bestimmte Bedingungen erfüllt sind und ein rekursiver Algorithmus den Aufruf stoppt sich selbst und beginnt, Werte zurückzugeben. Dies geschieht nur, wenn der rekursive Algorithmus bei jedem rekursiven Aufruf seinen Status ändert und sich in Richtung des Basisfalls bewegt.

Wenn die Rekursion nie endet, MUSS sie dann in die maximale Rekursionstiefe laufen.

Der einzige Fall, in dem Sie in Ihrem Code nicht auf dieses Problem stoßen, ist, wenn es keinen Hauptknoten gibt, sonst ist die Rekursion unendlich.

Es ist ein nettes Tool, mit dem Sie in den anderen Antworten zur Verfügung gestellt Ihr Code oder der Code visualisieren, was tut:

http://www.pythontutor.com/

, so dass Sie einen Eindruck von dem, was eigentlich los ist und wenn Das ist es, was Sie erreichen wollten.

Hier das Endergebnis Ausführen des Codes durch bones.felipe in der anderen Antwort auf Ihre Frage zu finden:

Der Kommentar zu Ihrer Frage nach FMc bereitgestellt gibt bereits eine sehr gute Antwort auf die Fragen, die Sie stellen (Zitat) :

Typischerweise hat ein BST drei Methoden: insert(), delete() und search(). Ihre aktuelle Implementierung führt zu verwirrenden Einträgen, indem sie einfügungsbezogenes Arbeiten (Erstellen eines Knotens) mit suchbezogener Arbeit durchführt. Es gibt auch eine verwandte Stilnotiz, die zu dieser allgemeinen Verwirrung beiträgt: Normalerweise sind Klassen Dinge oder Substantive (BinarySearchTree oder Node), nicht Aktionen (createnode oder createbinarysearchtree).

Answer 3

Es sieht aus wie Sie in jedem rekursiven Aufruf in auf das gleiche Objekt beziehen: unter Verwendung des ‚self.top‘ und nicht das Argument ‚top self.RecursBST (self.top.left, Daten) 'der Funktion. Probieren Sie etwas wie folgt aus:

class createnode: 
    def __init__(self,data): 
     self.root=data 
     self.left=None 
     self.right=None 

class createbinarysearchtree: 
    def __init__(self, data = None): 
     self.top=createnode(data) 

    def RecursBST(self,top,data): 
     if top is None: 
      return createnode(data) 
     if top.root is None: 
      top.root=data  
     elif top.root>data: 
      top.left=self.RecursBST(top.left,data) 
     elif top.root<data: 
      top.right=self.RecursBST(top.right,data)