Печать всех узлов в правом поддереве дерева двоичного поиска - PullRequest
Новая
       12

Печать всех узлов в правом поддереве дерева двоичного поиска

0 голосов
/ 16 марта 2020

Я довольно плохо знаком со структурами данных и рекурсией. Итак, я решил попробовать и реализовать метод, который печатал бы все значения всех узлов правого поддерева (в порядке возрастания, то есть: 50, 65, 72, 91, 99) в данном дереве, как опыт обучения. ,

Вот дерево, с которым я работаю визуально. The tree itself И у меня довольно много проблем с пониманием того, как выполнить рекурсию через правильное поддерево.

Это то, что я пытался сделать до сих пор (фактический метод находится внизу): 

class BinarySearchTree:
    _root: Optional[Any]
    # The left subtree, or None if the tree is empty.
    _left: Optional[BinarySearchTree]
    # The right subtree, or None if the tree is empty.
    _right: Optional[BinarySearchTree]

def __init__(self, root: Optional[Any]) -> None:
    """Initialize a new BST containing only the given root value.
    """
    if root is None:
        self._root = None
        self._left = None
        self._right = None
    else:
        self._root = root
        self._left = BinarySearchTree(None)
        self._right = BinarySearchTree(None)

def is_empty(self) -> bool:
    """Return True if this BST is empty.

    >>> bst = BinarySearchTree(None)
    >>> bst.is_empty()
    True
    """
    return self._root is None

# That is what I have tried doing so far.
def print_right_subtree(self) -> None:
    """Print the right subtree in order

    >>> bst = BinarySearchTree(41)
    >>> left = BinarySearchTree(20)
    >>> left._left = BinarySearchTree(11)
    >>> left._right = BinarySearchTree(29)
    >>> left._right._right = BinarySearchTree(32)
    >>> right = BinarySearchTree(65)
    >>> right._left = BinarySearchTree(50)
    >>> right._right = BinarySearchTree(91)
    >>> right._right._left = BinarySearchTree(72)
    >>> right._right._right = BinarySearchTree(99)
    >>> bst._left = left
    >>> bst._right = right
    >>> bst.print_right_subtree()
    50
    65
    72
    91
    99
    """
    if self.is_empty():
        pass
    else:
        # I am not really sure what to do here... 
        # I have tried setting self._left = None, but that just made things even more complicated!
        print(self._root)
        self._right.print_right_subtree()

Любая помощь будет чрезвычайно признательна! Кроме того, если у кого-то из вас есть учебник, которому я могу следовать, это было бы здорово для новичка ie, такого как я :).

Ответы [ 2 ]

2 голосов
/ 16 марта 2020

Если вы хотите напечатать узлы в правом поддереве, вам просто нужно вызвать ваш print_tree для атрибута вашего дерева, соответствующего его правому узлу.

Сначала вы определяете метод print_tree : 

def print_tree(self) -> None:
    if self.is_empty():
        pass
    else:
        # you are free to do additional things here such as print node value or etc..
        self._left.print_tree()
        self._right.print_tree()

А затем метод print_right_subtree : 

def print_right_subtree(self) -> None:
    self._right.print_tree() # which correspond to the print_tree of the _right attribute
1 голос
/ 16 марта 2020

Поскольку вы запрашиваете не сам код, а помощь в написании собственного кода ...

  1. Есть миллион способов сделать это. Некоторые из них более оптимизированы. Некоторые быстрее писать. Все зависит от того, что вам нужно.

  2. Здесь я думаю, что вам нужно понять, что такое дерево. Любое ваше поддерево, само по себе является деревом. Итак, вы должны понимать, что print the right tree означает все и вся. Например, только правая ветвь каждого дерева? Или все дерево первой правой ветви? Может быть, вторая ветвь?

  3. Если я правильно понял (Да, бум!), Вы хотите напечатать правую ветвь дерева, которая называется root в вашей схеме. Почему бы не сказать I want to print all the numbers above 41 вместо этого? Таким образом, даже если вы хотите распечатать свое дерево, начиная с поддерева, это будет действительно легко сделать!

  4. Вам нужно визуализировать, что будет делать ваш алгоритм. Здесь вы хотите напечатать все числа выше 41 (правая ветвь главного дерева). Позвольте мне написать вам псевдокод для этого (предположим, что вы уже находитесь на своем root узле со значением 65:

    • Я хочу записать все числа в порядке возрастания ...
    • Мой root - 65. Моему левому - 50, моему правому - 91.
    • Какой самый низкий? 50. У него есть другие ветви? Нет. Напечатайте это!
    • Мой root по-прежнему 65, мое право 91. Мой root ниже, чем моя ветвь? Распечатайте это! И go к правой ветви.
    • Мой основной теперь 91, мой слева 72, справа 99.
    • Какой самый низкий? Вы получили свою рекурсию.

И даже после всего этого вы могли бы все же решите сделать другое решение быстрее - писать, а не вычислять! - Соберите все значения из нужной вам ветви и выведите отсортированные значения!

...