Двоичные слова деревьев

Question

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

Answer 1

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

Имейте в виду, что при этом дерево очень элегантная структура. Это может показаться довольно сложным, но на каждом узле это просто. Чтобы выполнить операцию со всеми элементами дерева, вы просто выполняете эту операцию в корне дерева, а затем вызываете саму операцию для каждого дочернего элемента этого корня, которые сами являются корнями поддеревьев. Самостоятельная работа над примером поможет вам понять и принять рекурсию. Не сбивайтесь с толку, если вам трудно. Рекурсия странная. Поначалу это сложная концепция, но с деревьями нужно разбираться и работать.

Вот пример дерева (ASCII art), которое вы можете использовать для запуска:

      F
    /   \
   /     \
   D      H
 /  \    / \
 B   E  G   I
/ \
A  C

И простой алгоритм псевдокода, который вы можете использовать для написания всех букв в правильном порядке обхода.

procedure traverse(node)
    if node is not null:
        traverse(node.left)
        write node.letter
        traverse(node.right)
    else:
        do nothing

Вы можете даже начать с более простых деревьев. Что если дерево состоит только из узлов D, F и H? Что если бы это был только F? Ноль? Попробуйте эти простые примеры и перейдите к большему дереву. К тому времени, как вы научитесь делать это последовательно и правильно, у вас будет не только действительно хорошее представление о том, что происходит в реализации итератора, но и вы будете гораздо лучше понимать силу рекурсии.

Answer 2

У меня была такая же проблема в моем классе Data Structures.

Мое решение довольно простое.

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

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

Answer 3

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

Где пересекает ребенка означает (рекурсивно): 1) траверс левого ребенка 2) посмотреть на значение узла 3) траверс правого ребенка

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

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

Пример на python:

#!/usr/bin/env python

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

        def __str__(self):
            return "%d" % (self.value)

    def dfs(node = None):
        if node is None: return

        dfs(node.left)
        print node
        dfs(node.right)

    def bfs(root = None):
        if root is None: return

        nodes = []
        nodes.append(root)

        while len(nodes):
            current = nodes[0]
            print current
            nodes.remove(current)

        if current.left is not None:
            nodes.append(current.left)
        if current.right is not None:
            nodes.append(current.right)

    def main():
        root = Node(0)
        root.left = Node(10)
        root.right = Node(20)

        l = root.left
        l.left = Node(100)
        l.right = Node(101)

        r = root.right
        r.left = Node(200)
        r.right = Node(201)

        dfs(root)
        bfs(root)


    if __name__ == '__main__':
        main()



# example tree constructed:
#            0
#      10        20
#  100   101  200  201

# dfs (depth first) traversal:
# 100
# 10
# 101
# 0
# 200
# 20
# 201

# bfs (breadth first) traversal:
# 0
# 10
# 20
# 100
# 101
# 200
# 201

Answer 4

Есть 2 основных способа перебора дерева. Я опубликовал пример кода Python, описывающего, как это сделать, на Итеративное обход дерева *

Answer 5

Я могу сделать это рекурсивно. Я просто пытаюсь представить себе, как вы перемещаетесь от листа к листу, поскольку начиная с корня, есть 2 варианта, куда идти дальше, и после этого он просто увеличивается в 2 ^ n раз. Этот порядок того, как это работает, меня смущает.

Answer 6

Что вы подразумеваете под "итератором"? Если вам просто нужно перебрать дерево, вы можете сделать это рекурсивно: http://en.wikipedia.org/wiki/Tree_traversal#Sample_implementations

Если вам нужно предоставить интерфейс IEnumerator, как в C # или Java, или вы хотите сэкономить место в стеке, используйте это: http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal Вы можете использовать yield в C # или легко преобразовать цикл while в метод «GetNext», необходимый для итератора.