Понимание кода Википедии для общего поиска по дереву в глубину? - PullRequest
Новая
       60

Понимание кода Википедии для общего поиска по дереву в глубину?

4 голосов
/ 13 февраля 2012

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

  1. Обход по предварительному заказу
  2. Обход по предварительному заказу
  3. Обход по порядку

Далее в статье рассматривается первый обход произвольного (общего) дерева по глубине.Я вставил его здесь для удобства: 

// To traverse a non-empty tree in depth-first order,
// perform the following operations recursively at each node:
Perform pre-order operation
for i=1 to n-1 do
    Visit child[i], if present
    Perform in-order operation

Visit child[n], if present
Perform post-order operation

Вот все объяснения, которые Википедия предоставляет:

, где n - количество дочерних узлов.В зависимости от рассматриваемой проблемы операции предварительного заказа, заказа или последующего заказа могут быть недействительными, или вы можете захотеть посетить только определенный дочерний узел, поэтому эти операции следует считать необязательными.Кроме того, на практике может потребоваться более одной из операций предварительного заказа, заказа и последующего заказа.Например, при вставке в троичное дерево, операция предварительного заказа выполняется путем сравнения элементов.После этого может потребоваться операция после заказа, чтобы сбалансировать дерево.

Указанный алгоритм не имеет смысла для меня, поскольку он определен в терминах неопределенных операций:

  1. Предзаказ операции.
  2. Операция после заказа.
  3. Операция inorder.

Чтобы добавить к путанице, я не могу придумать определение для упомянутых операций, основанное на том, что я знаю и что присутствует в статье Википедии.Некоторое время я ломал голову над этим без каких-либо реальных достижений.У меня следующие вопросы:

  1. Неправильно ли указан алгоритм, указанный в статье в Википедии?Я подозреваю, что это так, но не могу сказать наверняка ничего, кроме того факта, что это плохо указано.
  2. Определяется ли первый порядок для общего дерева после заказа, предварительного заказа, глубины заказа даже для общего дерева?Они практически используются?Относится ли это к определению трех операций?Если так, то как?
  3. Если алгоритм действительно правильный, может кто-нибудь определить для меня вышеописанные операции и объяснить, как он работает?

1 Ответ

6 голосов
/ 13 февраля 2012

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

Вы можете думать о предварительном заказе, обходе и обратном заказевсе как частные случаи более общего алгоритма.В частности, предположим, что вы хотите выполнить обход дерева и выполнить некоторую операцию в определенное время во время поиска (либо предзаказ, либо порядок, либо порядок).Один из способов думать об этом заключается в том, что вы выполняете некоторую операцию предзаказа перед посещением текущего узла, некоторую операцию переупорядочения между посещением дочернего узла и самого узла и некоторую операцию после заказа после посещения узла.Любая из этих операций может быть «ничего не делать».Например, простой обход предзаказа будет определен как

  • Шаг предзаказа: выполните операцию, которую хотите сделать, предзаказ
  • Шаг переупорядочения: No-op
  • Postorderstep: No-op

Аналогичным образом, обход по почтовому заказу будет

  • Шаг предварительного заказа: No-op
  • Шаг Inorder: No-op
  • Шаг заказа: выполните операцию, которую хотите выполнить, заказ

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

  • Шаг предварительного заказа: добавить текущий узел в список «активных».
  • Шаг заказа: No-op
  • Шаг заказа.: Удалить текущий узел из «активного» списка.

Некоторые алгоритмы, такие как Алгоритм Тарьяна SCC , на самом деле делают такие вещи (хотя, по общему признанию, это алгоритм графа и вопросотносится к деревьям).Таким образом, код Википедии дает общий случай, в котором более частые случаи, плюс этот более сложный случай, являются особыми случаями.

Надеюсь, это поможет!

...