python двоичное дерево поиска

Question

По какой-то причине я не могу заставить метод «найти» работать. Я думаю, что это связано с проблемой определения области ... root.val, похоже, не обновляется глобально. Я получаю сообщение об ошибке, говорящее AtributeError: «INT» объект не имеет атрибута «Вэл» Вот мой код на данный момент:

class BinaryNode: 
    def __init__(self, v): 
     self.val = v 
     self.leftChild = None 
     self.rightChild = None 
    def get(self): 
     return self.val 
    def set(self, v): 
     self.val = v 
    def getChildren(self): 
     children = [] 
     if self.leftChild != None: 
      children.append(self.leftChild) 
     if self.rightChild != None: 
      children.append(self.rightChild) 
     return children 

class Tree: 
    def __init__(self): 
     self.root = None 
    def setRoot(self, node): 
     self.root = node 
    def size(self): 
     if self.root == None: 
      return 0 
    def subtreeSize(node): 
     return 1 + sum(subtreeSize(c) for c in node.getChildren()) 
     return subtreeSize(self.root) 

class BinarySearchTree(Tree): 
    def insert(self, val): 
     self.insertNode(self.root, val) 

    def insertNode(self, node, val): 
     if node is None: 
      self.setRoot(BinaryNode(val)) 
     elif val <= node.val: 
      node.leftChild = insertNode(BinaryNode(val), val) 
     elif val > node.val: 
      node.rightChild = insertNode(BinaryNode(val), val) 
     else: 
      node.val = val 


    def find(self, val): 
     self.findNode(self.root, val) 

    def findNode(self, node, val): 
     if node is None: 
      return False 
     elif val == node.val: 
      return True 
     elif val < node.val: 
      self.findNode(val, node.leftChild) 
     else: 
      self.findNode(val, node.rightChild) 


if __name__ == "__main__": 
    btree = BinarySearchTree() 
    vals = [5] 
    for v in vals: 
     btree.insert(v) 
    tests = [8, 5] 
    for t in tests: 
     print "find(%i) = %s" % (t, ("True" if btree.find(t) else "False")) 

Answer 1

Одна из проблем, с findNode() является то, что вам не хватает return заявления.

elif val < node.val: 
     self.findNode(val, node.leftChild) 
    else: 
     self.findNode(val, node.rightChild) 

следует читать

elif val < node.val: 
     return self.findNode(val, node.leftChild) 
    else: 
     return self.findNode(val, node.rightChild) 

У вас есть аналогичная проблема в insertNode().

Answer 2

Есть две проблемы с вашим методом findNode():

1. Вы перепутаны в node и val аргументы при вызове рекурсивно. Это заставляет ваш код попытаться найти .val на целочисленном значении вместо узла.

2. Вы забыли вернуть результаты рекурсивного вызова.

Уточненные методы:

def find(self, val): 
    return self.findNode(self.root, val) 

def findNode(self, node, val): 
    if node is None: 
     return False 
    elif val == node.val: 
     return True 
    elif val < node.val: 
     return self.findNode(node.leftChild, val) 
    else: 
     return self.findNode(node.rightChild, val) 

Ваша следующая проблема является ваш insertNode метод; вы пытаетесь вызвать глобальную функцию insertNode(); это, вероятно, должно быть self.insertNode(). Однако этот метод имеет no значение возврата, поэтому вы в конечном итоге устанавливаете node.leftChild или node.rightChild на None.

Вы хотите просто сдать поиск точки вставки в рекурсивном вызове, нет необходимости использовать возвращаемое значение:

def insert(self, val): 
    if self.root is None: 
     self.setRoot(BinaryNode(val)) 
    else: 
     self.insertNode(self.root, val) 

def insertNode(self, node, val): 
    if val <= node.val: 
     if node.leftChild: 
      self.insertNode(node.leftChild, val) 
     else: 
      node.leftChild = BinaryNode(val) 
    elif val > node.val: 
     if node.rightChild: 
      self.insertNode(node.rightChild, val) 
     else: 
      node.rightChild = BinaryNode(val) 

С этими изменениями, ваши простые тестовые отпечатки:

find(8) = False 
find(5) = True