Что не так с этой функцией поиска?

Question

class TreeNode:
    def __init__(self, _val):
        self._val = _val
        self._right = None
        self._left = None

    def search(self, val):
        if self._val == val:
            value = self._val
            return self
        if self._right is not None:
            right = self._right._val
            return self._right.search(val)
        if self._left is not None:
            left = self._left._val
            return self._left.search(val)

ПРИМЕР ВЫЗОВ:

a = TreeNode(3)
b = TreeNode(2)
c = TreeNode(4)
a.search(4)

Таким образом, это просто определяет класс treenode, а поиск должен принимать значение val и просто искать его при вызове в ROOT двоичного дерева . При запуске тестового примера он иногда возвращает правильный узел, иногда возвращает false, если я знаю, что он находится в дереве. Кто-нибудь знает, чем может быть вызвано это несоответствие?

Answer 1

Проблемы

• Если поиск self._right возвращает None (значение отсутствует нигде в правой ветви), ваш поиск немедленно будет return, не дойдя до self._left . Фактически, , пока существует self._right (не None), метод search никогда не проходит через self._left.
• Кроме того, вам необходимо убедиться, что вы связали перед запуском настройте свои узлы! Например, a._left = c.

Решение

Чтобы исправить это, я бы реализовал search следующим образом:

def search(self, val):
        if self._val = val:
            return self
        if self._right is not None:
            right = self._right.search(val)
            if right is not None:
                return right  # it’s okay to return now, we found something!
        if self._left is not None:  # if we’ve made it here, _right.search didn’t return
            return self._left.search(val)
        return None  # it’s good practice to explicitly return

Answer 2

a.search(3) будет работать, потому что значение a равно 3. Во всех остальных случаях этого не должно быть, потому что вы никогда не позволяли узлам подключаться. Для каждого из этих узлов, по крайней мере, на основании приведенного кода, нет левой или правой ветвей. Все они инициализируются значением None и никогда не устанавливаются на что-либо другое. Вы должны указать левую и правую ветку root, и тогда она должна работать.

Например, ваш класс должен иметь следующее:

def setLeft(self, node):
   self._left = node
def setRight(self, node):
   self._right = node

Затем используйте его как таковое:

a = TreeNode(3)
b = TreeNode(2)
c = TreeNode(4)
a.setLeft(b)
a.setRight(c)
a.search(4)

Конечно, вы должны изменить это в зависимости от того, как вы хотите структурировать дерево.

Answer 3

if self._right is not None:

Он остановит поиск и вернет результат поиска справа, если с self._right, и больше не будет поиска для левой стороны.

Здесь я изменил код и провожу тест.

import random

class Node():

    def __init__(self, value):
        self.value  = value
        self.left   = None
        self.right  = None

    def search(self, value):
        if self.value == value:
            return self
        result = None
        if self.left:
            result = self.left.search(value)
            if result:
                return result
        if self.right:
            result = self.right.search(value)
        return result

    def __repr__(self):
        return f'<Node value={self.value}>'

tree = {}
tree[0] = Node(0)

for i in range(1, 11):
    while True:
        parent = tree[random.choice(list(tree))]
        position = random.choice([0, 1])
        if (position==0 and parent.left) or (position==1 and parent.right):
            continue
        node = Node(i)
        tree[i] = node
        if position:
            parent.right = node
        else:
            parent.left = node
        break

root = tree[0]
for i in range(-5, 16):
    if i in tree:
        print(f'Value {i} found in {root.search(i)}')
    else:
        print(f'Value {i} not found')

Value -5 not found
Value -4 not found
Value -3 not found
Value -2 not found
Value -1 not found
Value 0 found in <Node value=0>
Value 1 found in <Node value=1>
Value 2 found in <Node value=2>
Value 3 found in <Node value=3>
Value 4 found in <Node value=4>
Value 5 found in <Node value=5>
Value 6 found in <Node value=6>
Value 7 found in <Node value=7>
Value 8 found in <Node value=8>
Value 9 found in <Node value=9>
Value 10 found in <Node value=10>
Value 11 not found
Value 12 not found
Value 13 not found
Value 14 not found
Value 15 not found