получить из двоичного дерева поиска

Question

Я работаю над двоичным деревом поиска в python. Но мой метод извлечения не работает, как я хочу. Он возвращает только правильное значение, когда я хочу получить root, и не возвращает ни одного для всех остальных узлов.

Вот мой код для моего класса узла:

class Treenode: 
    def __init__(self, item=None, left=None, right=None): 
     self.item = item 
     self.pleft = left 
     self.pright = right 
     self.parent = None 

    def __str__(self): 
     return str(self.item) 

Код для моего бинарного дерева:

from Treenode import * 
class Bintree: 
    def __init__(self): 
     self.root = None 
     self.size = 0 

    def insert(self, item): 
     self.size += 1 
     if self.root == None: 
      self.root = Treenode(item) 
     else: 
      self.insertnode(self.root, item) 

    def insertnode(self,node,item): 
     if node.pleft == None and node.pright == None: 
      if item > node.item: 
       newnode = Treenode(item) 
       node.pright = newnode 
       newnode.parent = node 
      else: 
       newnode = Treenode(item) 
       node.pleft = newnode 
       newnode.parent = node 
     else: 
      if item > node.item: 
       if node.pright != None: 
        self.insertnode(node.pright, item) 
       else: 
        newnode = Treenode(item) 
        node.pright = newnode 
        newnode.parent = node 
      else: 
       if node.pleft != None: 
        self.insertnode(node.pleft, item) 
       else: 
        newnode = Treenode(item) 
        node.pleft = newnode 
        newnode.parent = node     

    def print_inorder(self, root): 
     if root == None: 
      pass 
     else: 
      self.print_inorder(root.pleft) 
      print(root.item) 
      self.print_inorder(root.pright) 

    def print_postorder(self, root): 
     if root == None: 
      pass 
     else: 
      self.print_postorder(root.pleft) 
      self.print_postorder(root.pright) 
      print(root.item) 

    def print_preorder(self, root): 
     if root == None: 
      pass 
     else: 
      print(root.item) 
      self.print_preorder(root.pleft) 
      self.print_preorder(root.pright) 

    def retrieve(self, node, item): 
     if node == None: 
      return 'Empty Tree' 
     else: 
      if node.item == item: 
       return str(node) 
      elif node.item > item: 
       self.retrieve(node.pleft, item) 
      elif node.item < item: 
       self.retrieve(node.pright, item) 

Так что последний метод Bintree возвращает None для всех значений, кроме корня, но она должна вернуть значение узла.

заселение дерева:

import BinTree 
t = BinTree.Bintree() 
t.insert(10) 
t.insert(8) 
t.insert(15) 
t.insert(2) 
t.insert(0) 
t.insert(25) 
t.insert(1) 
t.insert(10) 
t.print_preorder(t.root) 
print('-----------------------') 
t.print_inorder(t.root) 
print('-----------------------') 
t.print_postorder(t.root) 
print('-----------------------') 
temp = t.retrieve(t.root, 10) 
print(temp) 

Answer 1

Ваша проблема в том что вы не возвращаются значения во всех путях вашего кода, следовательно, вы не видите ничего. Печатайте то, что не возвращает значение, печатает None. Измените свой метод извлечения следующим образом:

def retrieve(self, node, item): 
    if node == None: 
     return 'Empty Tree' 
    else: 
     if node.item == item: 
      return str(node) 
     elif node.item > item: 
      return self.retrieve(node.pleft, item) 
     elif node.item < item: 
      return self.retrieve(node.pright, item)