Nivåordning (BFS i träd)

Nivåordning börjar vid roten och besöker alla noder på djup noll, sedan djup ett, sedan två och så vidare. På ett oviktat rotat träd motsvarar detta breadth-first search (BFS). Till skillnad från preorder, inorder och postorder används en kö i stället för rekursiva djupet-först-anrop.

Exempel

För det binära exempelträdet blir ordningen A, B, C, D, E, F, G. Kön börjar med [A]. Ta ut A och lägg till B och C. Ta ut B och lägg till D och E. Därefter lägger C till F och G. Alla noder på tidigare nivå behandlas före nästa nivå.

Besöksordning hittills: –

Rekursionsstack: –

FöregåendeNästa stegBörja om

Försök förutsäga nästa nod innan du trycker på Nästa steg. Inorder är definierat för träd med vänster och höger barn.

Välj Nivåordning (BFS) och stega framåt. Kön visar de återstående noderna efter att barnen till den besökta noden har lagts till.

Implementationer

C#

C# | LevelOrder.cs

using System.Collections.Generic;

public sealed class Node
{
    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int value) => Value = value;
}

static List<int> LevelOrder(Node? root)
{
    var order = new List<int>();
    if (root is null) return order;
    var queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        Node node = queue.Dequeue();
        order.Add(node.Value);
        if (node.Left is not null) queue.Enqueue(node.Left);
        if (node.Right is not null) queue.Enqueue(node.Right);
    }
    return order;
}

C++

C++ | LevelOrder.cpp

#include <memory>
#include <vector>

struct Node {
    int value;
    std::unique_ptr<Node> left, right;
    explicit Node(int value) : value(value) {}
};

#include <queue>
std::vector<int> levelOrder(const Node* root) {
    std::vector<int> order;
    if (!root) return order;
    std::queue<const Node*> queue;
    queue.push(root);
    while (!queue.empty()) {
        const Node* node = queue.front(); queue.pop();
        order.push_back(node->value);
        if (node->left) queue.push(node->left.get());
        if (node->right) queue.push(node->right.get());
    }
    return order;
}

Komplexitet

Tiden är O(n) för n noder. Kön kan innehålla som mest en nivås bredd, vilket ger O(w) extra köminne för maximal bredd w (högst O(n)). Om hela resultatet sparas krävs dessutom O(n) utdatalagring. Trädets befintliga minne ingår inte i extraminnet.

Träd jämfört med grafer

Ett rotat träd har en unik väg från roten till varje nod. Därför krävs inget visited-set när man endast följer barnreferenser. Grafer kan däremot ha cykler och flera vägar till samma nod och kräver markering av besökta noder. Se BFS i grafer.

Övning: Rita ett träd med tre nivåer och förutsäg kön efter att roten har tagits ut. Vad ändras om höger barn köas före vänster?