Первая реализация поиска в глубине - понимание быстрого кода - PullRequest
Новая
       10

Первая реализация поиска в глубине - понимание быстрого кода

0 голосов
/ 25 декабря 2018

Я прошёл несколько уроков для Tree DS и нашел этот код, который действительно сбивает с толку, чтобы понять.Пожалуйста, объясните 

public func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self) // 1

        children.forEach { // 2
            $0.forEachDepthFirst(visit: visit)
        }
    }
}

Почему у нас здесь (само) посещение?

Я вижу объяснение здесь https://forums.raywenderlich.com/t/help-understanding-the-recursion-for-depth-first-traversal/56552/2, но оно до сих пор не ясно

Ответы [ 2 ]

0 голосов
/ 25 декабря 2018

Почему у нас visit(self) здесь?

Потому что, если бы мы этого не сделали, мы бы на самом деле не сделали бы ничего с любым из узлов надерево!

Рассмотрим это дерево: 

n1 -> n2 -> n3 -> n4

Теперь мы называем наш метод forEachDepthFirst для n1.Если бы у нас не было visit(self), мы бы немедленно позвонили forEachDepthFirst на n2, что вызвало бы его на n3, что вызвало бы его на n4.И тогда мы остановимся.Но ни в коем случае мы бы не назвали visit, поэтому мы бы перебрали все узлы дерева, не ничего не делая с этими узлами.

0 голосов
/ 25 декабря 2018

Любой рекурсивный метод имеет

1 - базовый случай: который завершает цикл, и вот он 

children.forEach // when children property is empty meaning a leaf node

2 - рекурсивный случай 

$0.forEachDepthFirst(visit: visit) // call the same method with it's children

Ваш метод требуетзамыкание / завершение, которое вызывается для каждого узла внутри основного корневого узла

Итак, предположим, у вас есть корневой 

0 
  - 1
     -  1.1 , 1.2 , 1.3

  -  2
     - 2.1 , 2.2 , 2.3

Здесь 0-ный узел вызывается тогда, когда запускается ваша функция

  • посещение (0)

  • children.forEach {// = 1,2

для 0> 1

  • посещение (1)

  • children.forEach {// = 1.1,1.2,1.3

для 0> 2

  • посещение (2)

  • children.forEach {// = 2.1,2.2,2.3

Внутренний корпус

для 0> 1> 1,1

  • посещение (1,1)

  • children.forEach {// заканчивается здесь, так как нет дочерних элементов (листовой узел)

и т. Д. Для 1,2,1,3

для 0> 2> 2.1 / 2.2 / 2.3 то же, что иприведенный выше случай

Как вызвать

Ваш метод является методом экземпляра внутри дерева, поэтому каждый узел может вызывать его, если вы хотите пересечь узлы 0затем сделайте это 

zeroNode.forEachDepthFirst {  (item) in
  print(item.name) // suppose node object has a name 
}

Тогда вы получите 

0 , 1 , 1.1 , 1.2 , 1.3 , 2.1 , 2.2 , 2.3

И это, как вы назвали visit(NodeObject) для основного узла и рекурсивно все его дочерние элементы

...