Inorder-traversering

Detta är en vanlig djupet-först-ordning för binära träd. Skillnaden är när den aktuella noden behandlas i förhållande till rekursionen i vänster och höger delträd.

Besöksordning

Vänster delträd, sedan roten, därefter höger delträd. För exempeltträdet med A som rot, B och C under, samt D/E och F/G längst ned, blir ordningen:

D, B, E, A, F, C, G.

Varje nod behandlas en gång. Det som ändras i koden är placeringen av output.Add eller push_back. Själva trädstrukturen är oförändrad.

Prova samma träd steg för steg

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äxla mellan ordningarna, förutsäg nästa markerade nod och studera de aktiva rekursionsanropen. Stacken visar vilka anrop som är aktiva när varje nod behandlas.

När passar ordningen?

Inorder är särskilt användbar för ett binärt sökträd eftersom ett korrekt strikt BST ger nycklarna i stigande ordning. Ett vanligt binärt träd blir inte automatiskt sorterat. Till skillnad från BFS följs en gren djupare innan återstående grenar behandlas.

C# och C++

C#

C# | Inorder.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 void Traverse(Node? node, List<int> output)
{
    if (node is null) return;
    Traverse(node.Left, output);
    output.Add(node.Value);
    Traverse(node.Right, output);
}

C++

C++ | Inorder.cpp

#include <memory>
#include <vector>

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

void traverse(const Node* node, std::vector<int>& output) {
    if (!node) return;
    traverse(node->left.get(), output);
    output.push_back(node->value);
    traverse(node->right.get(), output);
}

Komplexitet och avvägningar

Båda versionerna besöker var och en av n noder en gång, vilket ger O(n) tid. Rekursionsstackens extraminne är O(h) där h är trädets höjd. Utdatalistan tar dessutom O(n) om resultaten lagras. Om du behandlar värden direkt behöver du inte spara alla resultat. För balanserade binära träd är h O(log n); för skeva träd kan h bli O(n), vilket kan ge djup rekursion.

Övning: Vad blir ordningen i ett träd där roten bara har ett högerbarn? Vad ändras om du flyttar raden som lägger till resultatet?

Läs vidare om jämförelse av traversering och nivåordning.

Referens: W3Schools inorder.