Funktion einfügen für bst funktioniert nicht

Question

Wenn mir jemand mit dem Rekursionsteil helfen kann? Ich habe einen Teil weggelassen, der besagt, dass es nicht nötig war, aber danach funktionierte das nicht.

class node(object): 
    def __init__(self,value): 
     self.data=value 
     self.left=None 
     self.right=None 

def insert(Node,value): 
    if Node is None: 
     Node=node(value) 
    else: 
     if value<Node.data: 
##   if Node.left is None: Node.left=node(value) 
##   else: insert(Node.left,value) 
      insert(Node.left,value) 
     else: 
##   if Node.left is None: Node.left=node(value) 
##   else: insert(Node.left,value) 
      insert(Node.right,value) 

Answer 1

Da müssen Sie neue node Instanzen für Ihre leeren Zweige erstellen.

Mal sehen, was mit den beiden Definitionen geschieht, die Werte des Node Parameter Ausdrucken:

def insert(Node, value): 
    print(Node) 
    if Node is None: 
    Node=node(value) 
    else: 
    if value<Node.data: 
     insert(Node.left,value) 
    else: 
     insert(Node.right,value) 

Auf der REPL:

In [17]: badTree = node(10) 

In [18]: badTree.data 
Out[18]: 10 

In [20]: badTree.left.data 
---------------------------------------------------------------------- 
AttributeError      Traceback (most recent call last) 
<ipython-input-20-3cb52def2967> in <module>() 
----> 1 badTree.left.data 

AttributeError: 'NoneType' object has no attribute 'data' 

In [21]: badTree.right.data 
---------------------------------------------------------------------- 
AttributeError      Traceback (most recent call last) 
<ipython-input-21-b6f1267c9d29> in <module>() 
----> 1 badTree.right.data 

AttributeError: 'NoneType' object has no attribute 'data' 

Mal sehen, was passiert, wenn wir ein Element badTree einfügen :

In [22]: insert(badTree, 2) 
<__main__.node object at 0x7f706bf34d30> 
None 

In [23]: badTree.left.data 
---------------------------------------------------------------------- 
AttributeError      Traceback (most recent call last) 
<ipython-input-23-3cb52def2967> in <module>() 
----> 1 badTree.left.data 

AttributeError: 'NoneType' object has no attribute 'data' 

Es kann t nicht eingefügt werden Das Element, aber warum? In badTree, beide left und right Zweige sind None (leer), was bedeutet, dass wir dort neue Bäume erstellen müssen, da wir nicht in der Lage sein werden, neue Werte neu hinzuzufügen, da wir die Referenz auf die Haupt Node verlieren. Dies ist, wenn wir insert(Node.left, value) aufrufen, bevor ein neues Objekt zu Node.left zuweisen, wird es äquivalent sein insert(None, value) zu nennen (dies ist der Wert None, können Sie es sehen können, wenn wir insert auf badTree genannt), die rekursiv insert nennen und führen None = node(value) die wird nichts tun.

Was passiert, wenn wir diese Definition verwenden statt:

def insert(Node, value): 
    print(Node) 
    if Node is None: 
    Node = node(value) 
    else: 
    if value < Node.data: 
     if Node.left is None: 
     Node.left = node(value) 
     else: 
     insert(Node.left, value) 
    else: 
     if Node.right is None: 
     Node.right = node(value) 
     else: 
     insert(Node.right, value) 

Auf der REPL:

In [25]: newTree = node(4) 

In [26]: insert(newTree, 10) 
<__main__.node object at 0x7f706bf30668> 

In [27]: insert(newTree, 12) 
<__main__.node object at 0x7f706bf30668> 
<__main__.node object at 0x7f706bf30a58> 

Jetzt sehen, dass es nicht mehr geht nicht, wie wir den Überblick über die Speicheradressen zu halten sind in den Baumknoten und somit können wir auf diese Objekte (Bäume) verweisen, die uns die Insertionen an Ort und Stelle machen lassen.