BST-Einfügefunktion in Python

Question

Ich implementiere BST in Python und einige Probleme mit der Einfügefunktion.

class Node: 
    def __init__(self, val): 
     self.data = val 
     self.Leftchild = self.Rightchild = None 


class Tree: 
    def __init__(self): 
     self.root = None 

    def insert(self, val): 
     if self.root is None: 
      self.root = Node(val) 
      return self.root 
     else: 
      if self.root.data <= val: 
       self.root.Rightchild = self.insert(self.root.Rightchild, val) 
      else: 
       self.root.Leftchild = self.insert(self.root.Leftchild, val) 
      return self.root 
if __name__ == '__main__': 
    tree = Tree() 
    for i in range(10): 
     tree.insert(random.randint(0,100)) 

Ich habe TypeError auf rekursive.

TypeError: insert() takes 2 positional arguments but 3 were given 

Ist das nicht self.root.Rightchild oder self.root.Leftchild gleiche gilt als self? Wenn mein Gedanke falsch ist, wie kann ich rekursive Einfügefunktion in diesem Fall implementieren? Vielen Dank im Voraus!

Answer 1

1. Sie sollten insert nehmen ein weiteres Argument, root, und dass Ihre Operationen tun. Sie müssen auch die rekursive Logik ändern. Habe insert ausschließlich mit den Node Daten arbeiten.

2. Sie sollten Fälle behandeln, in denen ein Element bereits vorhanden ist. Du willst nicht, dass Duplikate in den Baum gelegt werden.

3. Im rekursiven Fall rufen Sie insert für das falsche Objekt an.

Auch sind die beiden nicht das Gleiche. self bezieht sich auf das aktuelle Objekt Tree, und self.root bezieht sich auf das aktuelle Tree Objekt Node, und so weiter.

---

Dies ist, wie Sie Ihre Funktion ändern würde: diese

def insert(self, root, val): 
    if root is None: 
     return Node(val) 

    else: 
     if root.data <= val: 
      root.Rightchild = self.insert(root.Rightchild, val) 
     else: 
      root.Leftchild = self.insert(root.Leftchild, val) 

     return root 

Answer 2

Versuchen ..

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


def inorder(root): 
    if root: 
     inorder(root.left) 
     arr.append(root.data) 
     print root.data, 
     inorder(root.right) 


def insert(root, data): 
    node = Node(data) 
    if root is None: 
     root = node 
    elif root.data >= data: 
     if root.left is None: 
      root.left = node 
     else: 
      insert(root.left, data) 
    else: 
     if root.right is None: 
      root.right = node 
     else: 
      insert(root.right, data) 
if __name__ == '__main__': 
    root = Node(50) 
    insert(root, 30) 
    insert(root, 20) 
    insert(root, 40) 
    insert(root, 70) 
    insert(root, 60) 
    insert(root, 80) 

    inorder(root) 

Answer 3

versuchen diese, wenn Sie Klasse und ihre Instanz benötigen

import random 
class Node: 
    def __init__(self, val): 
     self.data = val 
     self.Leftchild = self.Rightchild = None 


class Tree: 

    def insert(self,root, val): 
     if root is None: 
      root = Node(val) 
      return root 
     else: 
      if root.data <= val: 
       root.Rightchild = self.insert(root.Rightchild, val) 
      else: 
       root.Leftchild = self.insert(root.Leftchild, val) 
      return root 

    def inorder(self, root): 
     if root: 
      self.inorder(root.Leftchild) 
      print root.data, 
      self.inorder(root.Rightchild) 


if __name__ == '__main__': 
    tree = Tree() 
    root = None 
    for i in range(10): 
     root = tree.insert(root, random.randint(0,100)) 
    tree.inorder(root)