InOrder Traversal in Python

Question

Проблема, с которой я столкнулся, заключается в том, чтобы найти первый узел появления в обходном пути в BST. код у меня приводится ниже

def Inorder_search_recursive(node,key): 
    if not node: 
     return None 
    InOrder_search_recursive(node.lChild) 
    if node.value==key: 
     return node 
    InOrder_search_recursive(node.rChild) 

Этот код всегда возвращают None, что случилось с ним. Я думаю, что я возвращаю узел, когда я нахожу узел со значением k. Почему Питон не может передать этот узел ??? Заранее спасибо

Answer 1

Когда вы называете себя рекурсивно, как это:

InOrder_search_recursive(node.lChild) 

Это просто обычный вызов функции, как и любой другой. Он просто вызывает функцию и возвращает результат. Это не автоматически return значение из этой функции или что-то еще.

Итак, вы выполняете поиск по левому краю, игнорируете результаты, затем продолжаете проверять node.value == key и, если это не удается, вы выполняете поиск по правому поддереву, снова игнорируете результаты и падаете с конца функция, означающая, что вы возвращаете None.

Для выполнения этой работы вам необходимо указать return значение, которое вы получили. Но, конечно, только если это not None.

Кроме того, вы забыли передать аргумент key до рекурсивного вызова, так что вы просто получите TypeError. (Я предполагаю, что ваш реальный код не имеет эту проблему, но так как вы не показали нам свой реальный код, или рабочий пример, я не могу быть уверен, ...)

Итак:

def Inorder_search_recursive(node, key): 
    if not node: 
     return None 
    result = InOrder_search_recursive(node.lChild, key) 
    if result is not None: 
     return result 
    if node.value==key: 
     return node 
    return InOrder_search_recursive(node.rChild, key) 

(Вам не нужен not None проверку для поиска правой стороны, потому что, если она возвращает None, у нас нет ничего, чтобы попробовать и только собираемся вернуться None в любом случае.)

Answer 2

Поскольку ваша проблема to find the first occurrence node in its inorder traversal , вы должны 1) пересечь дерево в порядке и 2) остановиться, когда вы найдете первое вхождение.

def search(node, key): 
    if node is None: 
     return None 
    # Search the left subtree and return early if key is found 
    n = search(node.lChild, key) 
    if n is not None: 
     return n 
    # Check middle and return early if key is found 
    if node.value == key: 
     return node 
    # Search right subtree 
    return search(node.rChild, key) 

Answer 3

Мой другой ответ дает начинающему чистые решения, но если вы хотите более мощный и лаконичный ответ:

def Inorder_search_recursive_all(node, key): 
    if not node: 
     return 
    yield from InOrder_search_recursive(node.lChild, key) 
    if node.value==key: 
     yield node 
    yield from InOrder_search_recursive(node.rChild, key) 

Это создает все матчи в дереве, в порядке. И это дает вам их в качестве итератора, так что если вы просто хотите, чтобы первый, вы можете остановиться, как только вы найдете один, без впустую работы:

def Inorder_search_recursive(node, key): 
    return next(Inorder_search_recursive_all(node, key), None) 

Раздел учебник по Iterators и в следующем разделе, посвященном Генераторы объясняют, как это работает. Единственный недостающий бит - это объяснение yield from, что объясняется в PEP 380.