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.root.Leftchild認爲同self？ 如果我的想法錯了，在這種情況下如何實現遞歸插入功能？ 在此先感謝！

Answer 1

1. 你應該有insert採取另一種說法，root，並做你的操作。您還需要修改遞歸邏輯。請insert專門與Node數據一起使用。

2. 你應該處理一個項目已經存在的情況。你不想把重複項放入樹中。

3. 在遞歸的情況下，您對錯誤的對象調用insert。

另外，兩者不一樣。 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)