DFS в Swift не заканчивается - PullRequest
Новая
       7

DFS в Swift не заканчивается

0 голосов
/ 29 октября 2018

Моя реализация BFS работает нормально: 

func bfsReturnVals() -> [Int] {
    // bfs uses a queue.
    var queue = [Node]()
    var queueVals = [Int]()
    queue.append(self)
    while let head = queue.first {
        if let lft = head.left {
            queue.append(lft)
        }
        if let rgt = head.right {
            queue.append(rgt)
        }
        queueVals.append(queue[0].data)
        queue.removeFirst()
    }

    return queueVals
}

Но я обычно рекурсивно кодирую DFS. Теперь моя аналогичная реализация DFS не заканчивается 

func dfsReturnVals() -> [Int] {
    var stack = [Node]()
    var queueVals = [Int]()
    stack.append(self)
    while let tail = stack.last {
        if let lft = tail.left {
            stack.append(lft)
        }
        if let rgt = tail.right {
            stack.append(rgt)
        }
        queueVals.append(stack[stack.count - 1].data)
        stack.removeLast()
    }
    return queueVals
}

Я не могу понять, почему. Не должен ли removeLast () работать так же, как removeFirst ()?

Мой класс узлов выглядит следующим образом: 

class Node : CustomStringConvertible {
    var description : String {return "\(self.data)" }
    var data : Int
    var left: Node?
    var right: Node?

    init(_ data: Int) {
        self.data = data
    }

    func insert(_ data: Int) {
        if data < self.data {
            if let lft = self.left {
                lft.insert(data)
            } else {
                let newNode = Node(data)
                left = newNode
            }
        } else {
            if let rgt = self.right {
                rgt.insert(data)
            } else {
                let newNode = Node(data)
                right = newNode
            }
        }
    }
}

1 Ответ

0 голосов
/ 29 октября 2018

Когда вы удаляете последний элемент из стека, вы удаляете элементы, которые вы только что нажали.В вашей реализации bfs команда «удалить первым» будет захватывать предполагаемый родительский узел независимо от того, выполняете ли вы это в конце цикла, потому что вы добавляете дочерние элементы в конец очереди.Вам следует переместить операцию удаления расширенного узла из стека до того, как вы добавите новые узлы.

...