PythonでのBST挿入関数

Question

PythonでBSTを実装していて、挿入機能に問題があります。

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

再帰的にTypeErrorが発生しました。

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

はself.root.Rightchildまたはselfと同じと考えself.root.Leftchildはありませんか？ 私の考えが間違っている場合、どうすれば再帰的挿入機能を実装できますか？ ありがとうございます！

Answer 1

1. あなたは別の引数、rootを取り、そしてその上で、あなたの操作を行うinsert持っている必要があります。再帰的なロジックも変更する必要があります。 insertはNodeのデータで排他的に動作します。

2. アイテムが既に存在するケースを処理する必要があります。あなたはツリーに重複を入れたくありません。

3. 再帰的なケースでは、間違ったオブジェクトでinsertを呼び出しています。

また、2つは同じではありません。 selfは、現在のTreeオブジェクトを指し、self.rootは、現在のTreeのNodeオブジェクトなどを指します。

---

これはあなたの機能を変更したい方法です：

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

はこれを試してみてください。..

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

あなたはクラスとそのインスタンス

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) 

が必要な場合は、この方法を試してください。