Пройдите через двоичное дерево, используя dfs, останавливаясь в данной точке (в Python) - PullRequest
Новая
       20

Пройдите через двоичное дерево, используя dfs, останавливаясь в данной точке (в Python)

0 голосов
/ 20 февраля 2019

Я изучаю некоторые базовые концепции информатики.В качестве демонстрации я создаю скрипт на Python, который будет выполнять различные функции в двоичном дереве.Мне удалось успешно запрограммировать большинство из этих функций, за исключением одной конкретной.

Для двоичного дерева, созданного из массива целых чисел, я хотел бы сначала выполнить поиск в глубине для целого числа и вернуть путь, пройденный через дерево, до тех пор, пока это целое число не будет найдено в виде массива (последний номер в этом массиве - это номер, который искали).Как только будет найдено первое совпадение для этого целого числа, я хочу прекратить обход дерева.

Например, для dfs массива inorder [3,2,4,1,4,6,8,5] для целого числа 4 должно возвращаться [1,2,3,4]

Для целого числа 5 должно возвращаться [1,2,3,4,4,5] и т. Д.

Вот мой код: 

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

    def getValue(self):
        return self.value

def buildTree(array):
    print("building tree....")
    root=Node(array[0])
    del(array[0])
    for a in array:
        insert(root,Node(a))
    print("building complete")
    return root

def insert(root,node): 
    if root is None: 
        root = node 
    else: 
        if root.value < node.value: 
            if root.right is None: 
                root.right = node 
            else: 
                insert(root.right, node) 
        else: 
            if root.left is None: 
                root.left = node 
            else: 
                insert(root.left, node) 

def depthFirstSearch(root,target,results,subSearch):
#0:preorder
#1:inorder
#2:postorder
    if root!=None:

        if subSearch==0:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

        depthFirstSearch(root.left,target,results,subSearch)

        if subSearch==1:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

        depthFirstSearch(root.right,target,results,subSearch)

        if subSearch==2:
            results.append(root.getValue())
            if root.getValue()==target:
                return results

    return results

if __name__ == '__main__':
    #stuff that gets our arguments
    #...
    array=[3,2,4,1,4,6,8,5] #we would actually get this as an argument, but using this for example array
    target=4 #example target
    subSearch=1 #using inorder traversal for this example

    root=buildTree(array)
    results=[]
    results=depthFirstSearch(root,target,results,subSearch) 
    print(results) #expected:[1,2,3,4]

1 Ответ

0 голосов
/ 20 февраля 2019

Хорошо, это просто, просто используйте флаг «Дополнительная переменная», и тогда ваша функция становится 

def depthFirstSearch(root,target,results,subSearch, flag = 0):
#0:preorder
#1:inorder
#2:postorder
    if root!=None:

        if subSearch==0:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

        results, flag =depthFirstSearch(root.left,target,results,subSearch)
        if flag == 1:
            return results, flag
        if subSearch==1:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

        results, flag = depthFirstSearch(root.right,target,results,subSearch)
        if flag == 1:
            return results, flag

        if subSearch==2:
            results.append(root.getValue())
            if root.getValue()==target:
                return results, 1

    return results, flag

Здесь флаг изменяется на единицу и распространяется по мере сжатия стека функций, сохраняя их после каждого рекурсивного вызовапозаботьтесь об этом.

Также в основной функции вызов функции становится 

results, _=depthFirstSearch(root,target,results,subSearch)

Поскольку в определении функции присутствует flag = 0, вам просто нужно отбросить вторую переменную, вы даже можете использоватьчтобы проверить, был ли элемент найден в дереве, а не просто распечатать все дерево, если элемент отсутствует.

Если у вас есть какие-либо сомнения или сомнения, прокомментируйте ниже.

...