Реализация обхода бинарного дерева

Основываясь на том, что я понял о двоичном дереве, очереди и рекурсии, я реализовал этот алгоритм поиска в ширину следующим образом. Есть ли у вас какие-либо предложения по его улучшению (с точки зрения читаемости, передовой практики и т. Д.)?

# Definition for a binary tree node.
class Node(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def preorder_print(self):
        print(self.val)
        if self.left:
            self.left.preorder_print()
        if self.right:
            self.right.preorder_print()
        return
    
    def postorder_print(self):
        if self.left:
            self.left.postorder_print()
        if self.right:
            self.right.postorder_print()
        print(self.val)
        return

    def inorder_print(self):
        if self.left:
            self.left.inorder_print()
        print(self.val)
        if self.right:
            self.right.inorder_print()
        return

    def bread_traversal_print(self):
        q=Queue()
        q.push(self)
        def bt():
            #import pdb;pdb.set_trace
            if not q:
                return
            node=q.pop()
            if node:
                if  node.left:
                    q.push(node.left)
                if  node.right:
                    q.push(node.right)
                print(node.val)
                bt()
        bt()
        

class Queue():
    def __init__(self):
        self.data = []

    def push(self,elt):
        self.data.append(elt)
    
    def pop(self):
        if self.data:
            return self.data.pop(0)
    def peek(self):
        if self.data:
            return self.data[0]

if __name__ == "__main__":
    #input = [l for l in 'FDJBEGKACIH']
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)

    print("preorder:")
    root.preorder_print()
    print("postorder:")
    root.postorder_print()
    print("inorder:")
    root.inorder_print()

    print('bread :')
    root.bread_traversal_print()

    """          1
            2       3
        4     5    6  7

    [1 2 4 5 3 6 7]

    """



РЕДАКТИРОВАТЬ: Да, BFS для поиска в ширину будет более подходящим;)

1 ответ
1

Определение класса

Нет необходимости явно наследовать от object; это анахронизм Python 2.x.

Вместо того class Node(object):просто напишите class Node:.

Так же, class Queue(): может просто быть class Queue:.

Параметры по умолчанию

Каждые Node должен иметь значение; мало причин для указания значения по умолчанию 0 для val параметр. Вынуждая вызывающего абонента предоставить значение, вы с меньшей вероятностью случайно получите узел с целым числом по умолчанию. 0 значение, когда все остальные узлы созданы с (скажем) строками.

Ненужные возвраты

Нет необходимости в return заявления в preorder_print, postorder_print, и inorder_print.

Шаблон посетителя

Вы определили несколько методов обхода дерева. Все они печатают значения. Если вы хотели сделать что-нибудь еще со значениями, вы застряли в написании другой (набор из 4?) Функций.

Вместо этого вы должны отделить обход от операции. Посетите каждый узел в определенном порядке и сделайте что-нибудь в этом узле.

class Node:

    ...

    def preorder(self, visitor):
        visitor(self.val)
        if self.left:
            self.left.preorder(visitor)
        if self.right:
            self.preorder(visitor)

    ...

# Do a pre-order traversal the tree, starting at the root, printing each values.
root.preorder(print)

Первый обход в ширину

Во-первых, вероятно, следует вызвать функцию breadth_traversal_printне bread_traversal_print.

Во-вторых, нет необходимости использовать рекурсию во время обхода в ширину. У тебя есть Queue который отслеживает узлы, которые вам нужно посетить. Вам просто нужно зациклить while очередь не пуста. Рекурсия делает цикл ресурсоемким. Если бы в Python была оптимизация хвостового вызова, неэффективность могла бы быть устранена автоматически; но Python этого не делает, поэтому такой цикл неверен.

    def breadth_traversal_print(self):
        q = Queue()
        q.push(self)

        while q:
            node = q.pop()
            if node:
                if node.left:
                    q.push(node.left)
                if node.right:
                    q.push(node.right)
                print(node.val)

PEP-8

В PEP 8 – Руководство по стилю для Python перечисляет множество рекомендаций по стилю, которым должны следовать все программы.

Белое пространство

Вокруг бинарных операторов должен быть пробел, например =. Вы нарушаете это с помощью q=Queue(). Обратите внимание, что = используется с ключевым словом arguments не является оператором, поэтому не должен быть окружен пробелами; следовательно def __init__(self, val=0, left=None, right=None): верно.

После запятых должен быть пробел. Вы нарушаете это в def push(self,elt):

Код без операции

Эта строка …

    """          1
            2       3
        4     5    6  7

    [1 2 4 5 3 6 7]

    """

… это утверждение, которое ничего не делает и не имеет побочных эффектов. Возможно, вы имели в виду, что это комментарий?

ПРИМЕЧАНИЕ: Это отличается от """docstrings""". Строковый оператор, следующий сразу за class или def оператор обрабатывается как строка документации, удаляется из программного кода и сохраняется в __doc__ член класса или функции интерпретатора Python. Там его можно извлечь help(...) и другие программы создания документации.

  • Что касается последнего комментария, это фактически не строка, а комментарий, помогающий визуализировать тестовый пример в части if name = main! Является ли плохой практикой включать такую ​​строку, чтобы помочь читателю понять тестовый пример?

    – любопытно

  • Если это комментарий, то синтаксически его следует записать как комментарий, а не как строку. Что касается визуализации тестового примера, он ниже тестового примера обхода в ширину, но показывает список результатов предварительного заказа из нескольких предыдущих тестов. Выполнение четырех «тестовых примеров», но отображение результатов только для одного из них и отсутствие необходимости указывать, какой именно, не совсем помогает читателю.

    – AJNeufeld

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *