Лаб. 07: Связные списки, изменяемые деревья

Основная часть

После завершения работы над каждым вопросом фиксируй изменения (делай коммит):

$ git add .
$ git commit -m "Решение вопроса X"

Так же не возбраняется в любое время проталкивать изменения на GitHub:

$ git push

Вопрос 1: Связные списки (ПСП)

Изучи класс Link.

class Link:
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ', '
            self = self.rest
        return string + str(self.first) + '>'

    @property
    def second(self):
        return self.rest.first

    @second.setter
    def second(self, value):
        self.rest.first = value

А теперь примени знания на практике.

>>> link = Link(1000)
>>> link.first
______
>>> link.rest is Link.empty
______
>>> link = Link(1000, 2000)
______
>>> link = Link(1000, Link())
______
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______
>>> link.rest.first
______
>>> link.rest.rest.rest is Link.empty
______
>>> link.first = 9001
>>> link.first
______
>>> link.rest = link.rest.rest
>>> link.rest.first
______
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first
______
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______
>>> link2.rest.first
______
>>> link = Link(5, Link(6, Link(7)))
>>> link.second
______
>>> link.rest.second
______
>>> link.second = 10
>>> link        # Посмотри на метод __repr__ класса Link
______
>>> link.second = Link(8, Link(9))
>>> link.second.first
______
>>> print(link)  # Посмотри на метод __str__ класса Link
______

Вопрос 2: Деревья (ПСП)

Изучи класс Tree.

class Tree:
    """Дерево — это метка и список ветвей."""
    def __init__(self, label, branches=[]):
        self.label = label
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def __repr__(self):
        if self.branches:
            branch_str = ', ' + repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(repr(self.label), branch_str)

    def __str__(self):
        return '\n'.join(self.indented())

    def indented(self):
        lines = []
        for b in self.branches:
            for line in b.indented():
                lines.append('  ' + line)
        return [str(self.label)] + lines

    def is_leaf(self):
        return not self.branches

Теперь, по-прежнему считая себя Пайтоном, заполни пропуски.

>>> t = Tree(1, Tree(2))
______
>>> t = Tree(1, [Tree(2)])
>>> t.label
______
>>> t.branches[0]
______
>>> t.branches[0].label
______
>>> t.label = t.branches[0].label
>>> t
______
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______
>>> t.branches[0]
______
>>> t.branches[1]
______

Вопрос 3: Link2List

Напиши функцию link_to_list, которая принимает связный список, а возвращает Python-список с теми же элементами. Считай, что исходный связный список не содержит других связных списков.

Попробуй решить эту задачу и итеративно, и рекурсивно!

def link_to_list_iter(link):
    """Принимает связный список и возвращает Python-список с теми же элементами.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list_iter(link)
    [1, 2, 3, 4]
    >>> link_to_list_iter(Link.empty)
    []
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def link_to_list_rec(link):
    """Принимает связный список и возвращает Python-список с теми же элементами.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list_rec(link)
    [1, 2, 3, 4]
    >>> link_to_list_rec(Link.empty)
    []
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 4: Хранение цифр

Напиши функцию store_digits, которая принимает целое число n и заносит образующие его цифры в связный список.

def store_digits(n):
    """Возвращает связный список цифр числа n.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 5: Накопительная сумма

Напиши функцию cumulative_sum, которая изменяет дерево t так, что значение в каждом узле становится суммой всех узловых значений в соответствующем поддереве c корнем в t.

def cumulative_sum(t):
    """Изменяет t так, что значение в каждом узле
    становится суммой всех узловых значений в соответствующем
    поддереве c корнем в t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(t)
    >>> t
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 6: BST ли?

Напиши функцию is_bst, которая принимает дерево t и возвращает True, если и только если t является корректным двоичным деревом поиска, что, кстати, значит:

  • Каждый узел имеет не более двух ветвей (лист является корректным двоичным деревом поиска на автомате).

  • Каждая ветвь является корректным двоичным деревом поиска.

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

  • Для каждого узла справедливо утверждение, что элементы правой ветви больше значения текущего узла.

Заметь, что узел с единственной ветвью может отнести её и к правому случаю, и к левому. Имей это ввиду.

Возможно, неплохой идеей будет написать вспомогательные функции bst_min и bst_max, которые будут возвращать минимум и максимум соответственно. 
def is_bst(t):
    """Возвращает True, если дерево t имеет структуру бинарного дерева поиска.

    >>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
    >>> is_bst(t1)
    True
    >>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
    >>> is_bst(t2)
    False
    >>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
    >>> is_bst(t3)
    False
    >>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
    >>> is_bst(t4)
    True
    >>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
    >>> is_bst(t5)
    True
    >>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
    >>> is_bst(t6)
    True
    >>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
    >>> is_bst(t7)
    False
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 7: Центрированный обход

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

def in_order_traversal(t):
    """
    Функция-генератор, которая совершает центрированный обход дерева,
    последовательно выдавая результаты. Считай, что каждый узел
    может содержать от 0 до 2 веток.

    Например, для такого дерева t:
            1
        2       3
    4     5
         6  7

    последовательность центрированного обхода будет 4, 2, 6, 5, 7, 1, 3

    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5, [Tree(6), Tree(7)])]), Tree(3)])
    >>> list(in_order_traversal(t))
    [4, 2, 6, 5, 7, 1, 3]
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Дополнительная часть

Вопрос 8: Удали всё

Создай функцию remove_all, которая принимает связный список link и значение value. Функция должна удалить все узлы, содержащие значение value. Считай, что связный список link сдержит по крайней мере один узел, и что первый элемент списка никогда не удаляется. Заметь, что возвращать ничего не надо. Изменять надо переданный список, а не его копию.

def remove_all(link , value):
    """Удаляет все элементы связного списка link, содержащие значение value.
    Считай, что есть элементы для удаления и первый элемент никогда не удаляется.

    >>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
    >>> print(l1)
    <0, 2, 2, 3, 1, 2, 3>
    >>> remove_all(l1, 2)
    >>> print(l1)
    <0, 3, 1, 3>
    >>> remove_all(l1, 3)
    >>> print(l1)
    <0, 1>
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 9: Изменяющее отображение

Разработай функцию deep_map_mut(fn, link), применяющую функцию fn ко всем элементам списка link. Если элемент списка также является списком, то отображение нужно применить и к его элементам. Это должно работать для произвольной глубины вложения.

Функция должна изменять исходный список. Создавать новые связные списки не нужно.

Возможно, тебе пригодится встроенная функция isinstance.

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False
 
def deep_map_mut(fn, link):
    """Изменяет все элементы связного списка link, применяя к их значениям
    функцию fn. Не создаёт новые объекты Link (то есть не использует конструктор Link)

    Не возвращает изменённый объект.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> deep_map_mut(lambda x: x * x, link1)
    >>> print(link1)
    <9, <16>, 25, 36>
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 10: Циклы

Класс Link может моделировать списки с циклами. То есть список может содержать сам себя в качестве подсписка.

>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3

Создай функцию has_cycle, которая проверяет наличие циклов в связном списке.

Перебирай элементы связного списка и запоминай, какие уже были посещены. 
def has_cycle(link):
    """Проверяет наличие цикла в связном списке.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    >>> u = Link(2, Link(2, Link(2)))
    >>> has_cycle(u)
    False
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Если ты решал с оглядкой на совет перед кодом, скорее всего сейчас функция требует линейного пространства. Попробуй дополнительно создать функцию has_cycle_constant, которой требуется константное пространство. Решение довольно короткое — менее 20 строк кода, но нужна хорошая идея. Попробуй решить самостоятельно.

def has_cycle_constant(link):
    """Проверяет наличие цикла в связном списке.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 11: Переворот через одного

Напиши функцию reverse_other, которая изменяет дерево так, что последовательность узловых значений на всех нечетных уровнях обращается. Например, дерево Tree(1,[Tree(2, [Tree(4)]), Tree(3)]) превращается в Tree(1,[Tree(3, [Tree(4)]), Tree(2)]). Имей в виду, что ветви остаются на местах. Изменяются только узловые значения.

def reverse_other(t):
    """Изменяет дерево t так, что в узлах на нечётной
    глубине последовательность узловых значений разворачивается.

    >>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(4), Tree(3), Tree(2)])
    >>> t = Tree(1, [Tree(2, [Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])]), Tree(8)])
    >>> reverse_other(t)
    >>> t
    Tree(1, [Tree(8, [Tree(3, [Tree(5), Tree(4)]), Tree(6, [Tree(7)])]), Tree(2)])
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"