Arrayrepresentation av binära träd

Ett komplett binärt träd passar bra i en array. Lagra noderna i nivåordning, från vänster till höger. Vid nollbaserad indexering ligger roten på index 0, vänster barn till index i på 2*i + 1 och höger barn på 2*i + 2. Förälder till index i > 0 är (i - 1) / 2 med heltalsdivision.

Exempel

Om A är rot, B och C dess barn och D och E är B:s barn, kan trädet lagras som [A, B, C, D, E]. B ligger på index 1, därför finns barnen på 3 och 4. C ligger på 2, och dess vänsterposition skulle vara 5, utanför arrayen.

Varför formlerna fungerar

Varje komplett nivå har dubbelt så många positioner som den föregående. Med BFS-ordning hamnar barnen efter de tidigare föräldrarnas barn. Vid ettbaserad indexering ändras formlerna till 2*i och 2*i+1. Blanda inte konventionerna.

C#

C# | ArrayTree.cs

using System.Collections.Generic;
static bool TryLeft<T>(IReadOnlyList<T> values, int index, out T child)
{
    long left = 2L * index + 1;
    if (index >= 0 && left < values.Count)
    {
        child = values[(int)left];
        return true;
    }
    child = default!;
    return false;
}

C++

C++ | ArrayTree.cpp

#include <vector>
#include <cstddef>

template<class T>
bool tryLeft(const std::vector<T>& values, std::size_t i, T& child) {
    if (i >= values.size() || i > (values.size() - 1) / 2) return false;
    std::size_t left = 2 * i + 1;
    if (left >= values.size()) return false;
    child = values[left];
    return true;
}

Begränsningar och kostnad

Att läsa ett känt barnindex är O(1), men genomgång av n noder tar fortfarande O(n) tid. Själva arrayen använder O(n) utrymme. Ett godtyckligt glest träd kan behöva markörer för tomma positioner eller en länkad representation. Ta inte bort platshållare mitt i arrayen utan att räkna om alla index för efterkommande noder.

Vanligt misstag: 2*i+2 kan ge overflow för mycket stora index. Kontrollera gränser och använd lämplig heltalstyp. Exemplet kontrollerar indexet mot samlingens längd men förutsätter ändå rimlig storlek.

Läs vidare om trädtyper och nivåordning.

Referens: W3Schools arrayimplementering.