Python-Как реализовать дерево абстрактный тип данных?

Question

Например, двоичное дерево поиска имеет запись 5; он имеет две ветви, у которых оставленная запись узла равна 2, а справа - 7. Каждый узел имеет также две ветви: для входа в узел 2 он оставил запись узла 1 и запись 3 правого узла; для входа 7 узла он оставил запись узла 6 и правый узел 10 и 8 узла. Чтобы посетить записи узлов в правильном порядке, сначала перейдите в левую ветвь ([1,2], а затем 3); затем посетите 5; наконец, посетить правую ветвь (сначала [6,7], а затем [8,10])

Как создать функцию «binary_tree (entry, left, right)», чтобы получить выход абстрактных данных дерева вместо используя функции, отсортированные или отсортированные.? И как определить запись (дерево), left_branch (дерево) и right_branch (дерево)?

Answer 1

По определению аннотация класс является одним из них вы не можете напрямую экземпляр; скорее, вы создаете бетон классы (обычно подклассы абстрактного), реализующие его.

Таким образом, определить интерфейс программирования вы хотите для своего абстрактного класса: например, в Python 2 (это немного более элегантно в Py 3, но эквивалент):

import abc 

class AbstractTree(object): 
    __metaclass__ = abc.ABCMeta 

    @abc.abstractmethod 
    def entry(self): return 

    @abc.abstractmethod 
    def left(self): return 

    @abc.abstractmethod 
    def right(self): return 

, а затем один или более конкретные подклассы , и использовать последний.

Например:

class SimpleTree(AbstractTree): 

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

    def entry(self): return self.entry 

    def left(self): return self.left 

    def right(self): return self.right 

Обратите внимание, что это совершенно аномальный случай, так как конкретный класс получает не функциональность от этого пустого абстрактного класса - в реальной жизни, то есть для дидактических целей, за исключением, я бы не использовать абстрактные классы для этого случая, так как здесь нет добавленной стоимости. Тем не менее, если вы настаиваете, вот как вы это делаете :-).

Аналогично для вспомогательной функции вы указываете (здесь я переключение на Py 3, как элегантность неотразимым-х):

def binary_tree_generator(entry, left, right): 
    if left is not None: 
     yield from binary_tree_generator(left.entry, left.left, left.right) 
    yield entry 
    if right is not None: 
     yield from binary_tree_generator(right.entry, right.left, right.right) 

def binary_tree(entry, left, right): 
    for anentry in binary_tree_generator(entry, left, right): 
     print(anentry) 

В реальной жизни, я бы сделал это метод AbstractTree, не как вам нужно. Аналогично для других трех вспомогательных функций, которые вы указываете, которые точно дублируют методы getter абстрактного класса ...!

EDIT: по-видимому, прилагательное абстрактный перегружен достаточно, что Q является не о собственных абстрактных базовых классов Python, но более, ну, абстрактный смысл слова «абстрактный» (!). В этом случае можно было бы например отобразить каждый узел дерева в кортеж 3-х предметов (если узлы дерева являются неизменными):

(entry, left, right) 

до сих пор используют None для представления «отсутствует» left и right детей; в этом случае, функции доступа, очевидно, будет

def entry(tree): return tree[0] 
def left_branch(tree): return tree[1] 
def right_branch(tree): return tree[2] 

и запрошенная функция, которая делает упорядоченную прогулку на дереве будет использовать генератор типа (возвращаясь к py2-совместимый код :-) .. ,:

def binary_tree_generator(the_entry, left, right): 
    if left is not None: 
     for an_entry in binary_tree_generator(
      entry(left), left_branch(left), right_branch(left)): 
      yield an_entry 
    yield the_entry 
    if right is not None: 
     for an_entry in binary_tree_generator(
      entry(right), left_branch(right), right_branch(right)): 
      yield an_entry 

Я до сих пор с помощью генератора, потому что это настолько очевидно, что «только один правильный способ сделать это» для прогулок дерева (с возможностью выбора, что делать с каждой записью, будь print ИНГ его или иным образом, явно принадлежащие к другой функции, петляющей над этим генератором!). Но я переключился на Py2-совместимые петли yield an_entry, так как это делает тривиальным заменять каждый yieldprint, если это требуется домашней работой.

Я изменил имена из спецификации добротности, потому что функции добротности в полностью сломаны WRT именование - они требуют, чтобы местный аргумент (первый) будет называться entry но также функции аксессора для входа узел дерева должен быть тождественно с именем entry - причиной совершенно ненужного конфликта имен [*]. Поэтому я сохранил имя entry только для функции accessor и переключился на the_entry для имени аргумента и an_entry для другой локальной переменной, необходимой в петлях for.

[*] его можно решить, например, используя globals()['entry'] для доступа к затененному глобальному имени, но это просто глупо ставить себя сознательно в положение, необходимое для достижения таких «проходов в Hail Mary», противоречивые имена в первую очередь намного проще! -)