ДФС в двоичное дерево


Постановка задачи: проанализировать глубину первого обхода на БСТ и печатать используемых элементов.

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

class BST(object):
    def __init__(self, value):
        self.root = Node(value)

    def insert(self, value):
        current = self.root
        while current:
            if value > current.value:
                if current.right is None:
                    current.right  = Node(value)
                    break
                else:
                    current = current.right
            else:
                if current.left is None :
                    current.left  = Node(value)
                    break
                else:
                    current = current.left

    def preorder(self,root):
## root,left,right

        if root:
            print root.value
            if root.left:
                self.preorder(root.left)
            if root.right:
                self.preorder(root.right)


    def postorder(self,root):
## left, right, root

        if root:
            if root.left:
                self.postorder(root.left)
            if root.right:
                self.postorder(root.right)
            print root.value


    def inorder(self,root):
## left, root, right

        if root.left:
            self.inorder(root.left)
        print root.value
        if root.right:
            self.inorder(root.right)



t = BST(100)
t.insert(12)
t.insert(92)
t.insert(112)
t.insert(123)
t.insert(2)
t.insert(11)
t.insert(52)
t.insert(3)
t.insert(66)
t.insert(10)
print "preorder traversal is this "
t.preorder(t.root)
print "postorder traversal is this "
t.postorder(t.root)
print "inorder traversal is this "
t.inorder(t.root)

Как этот код более эффективным?



Комментарии
2 ответа

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


  1. Вместо того, чтобы называть свой бинарный поиск-класс дерево БСТ определить его как

    class BinarySearchTree(object):
    # remainder of your code

    Дает больше смысла в название класса.


  2. Предзаказ обхода называется как t.preorder(t.root). Но подождите, t уже имеет корневой узел в нем, так это будет гораздо более читабельным, если мы могли бы сделать t.preorder(). Чтобы изменить подпись на:

    def preorder(self, root=None):
    if root is None:
    root = self.root
    # remainder of your code

Же самое должно быть сделано для t.inorder() и t.postorder() как хорошо.


  1. Места: вам нужно пространство между ваши аргументы, как это рекомендовано Пеп-0008. Так что def inorder(self, root): вместо def inorder(self,root):. Это касается inorder и postorder также

  2. Использовать корень в качестве аргумента название вводит в заблуждение - его лучше назвать это как узел, который имеет значение по умолчанию self.root. Это чище, так как в ДФС, вы бы перебрать все узлы дерева.

    def preorder(self, node=None):
    # replace root with node in your code

    Же самое должно быть сделано для inorder и postorder как хорошо.


  3. Комментарии и отступы: ваши комментарии не с отступом вправо. Вместо того

        def inorder(self,root):
    ## left, root, right

    Попробовать defing их в виде строки документации

    def inorder(self,root):
    """traversal order: left child node, current node, right child node"""
    # remainder of your code

7
ответ дан 13 апреля 2018 в 06:04 Источник Поделиться

этот код уже выглядит неплохо, особенно если учитывать советы других ответить

возвращаемое значение

Одна проблема, я хоть вижу, что если вы хотите использовать дерево для чего-то другого, чем печатать, это невозможно. Это можно легко исправить, сделав обыски в итераторы, а затем распечатать элементы

def inorder(self, node=None):
"""traversal order: left child node, current node, right child node"""
if node is None:
node = self.root
if node.left:
for node in self.inorder(node.left)
yield node
yield node.value
if node.right:
for node in self.inorder(node .right)
yield node


for node in t.inorder(t.root)
print(node)

Получение узла

Я не вижу способа сделать узел?

Добавить несколько узлов

Возможно, есть способ, чтобы добавить несколько узлов одновременно облегчит инициализации

альтернативный подход

Другой подход мог бы дать обход методом Node вместо дерева. Можно даже сделать универсальный Node.traversal способ

def traverse(self, order=('left', 'self', 'right'):
orders = {
'inorder': ('left', 'self', 'right',),
'preorder': ('self', 'left', 'right',),
'postorder': ('left', 'right', 'self',),
'reverse': ('right', 'self', 'left',),
}

try:
order = orders[order]
except KeyError, TypeError:
errormsg = ''''order should be one of {} or only contain ('left', 'self', 'right')'''.format(set(orders.keys()))
assert set(order) <={'left', 'self', 'right'}, errormsg

for element in order:
if element == 'left' and self.left is not None:
yield from self.left.traverse(order=order)
if element == 'self'
yield self.value
if element == 'right' and self.right is not None:
yield from self.right.traverse(order=order)

Этот код, вероятно, будет немного медленнее, чем специализированный метод для каждого режима обхода, но он более универсален и содержит меньше повторов, так проще с точки зрения обслуживания

5
ответ дан 14 апреля 2018 в 09:04 Источник Поделиться