Clasa a XI-a · ArboriRead in English

Fiii, descendenții și ascendenții unui nod în C++

În engleză: Children, descendants and ancestors of a node

O(n²)C++1792 de linii2 exemple

Ideea

Arborele este dat prin vectorul de tați (t[rădăcină] = 0). Fiii lui x sunt nodurile i cu t[i] = x. Un nod y este descendent al lui x dacă, urcând din y din tată în tată, ajungem în x. Ascendenții lui x sunt nodurile întâlnite urcând din x până la rădăcină: tatăl, bunicul etc. Se afișează fiii și descendenții în ordine crescătoare, iar ascendenții de la tată spre rădăcină („niciunul” dacă nu există).

Descrierea în engleză

The tree is given by its parent array (t[root] = 0). The children of x are the nodes i with t[i] = x. A node y is a descendant of x if, climbing from y from parent to parent, we reach x. The ancestors of x are the nodes met climbing from x up to the root: the parent, the grandparent and so on. The children and descendants are printed in increasing order, and the ancestors from the parent up to the root ('niciunul' (none) if there are none).

Complexitate
O(n · h), unde h este înălțimea arborelui
Clasa
Clasa a XI-a (Grade 11)
Capitol
Arbori

Exemple

Exemplul 1

Intrare

8
3 3 0 1 1 2 4 2
1

Ieșire așteptată

Fii: 4 5
Descendenti: 4 5 7
Ascendenti: 3
Exemplul 2

Intrare

8
3 3 0 1 1 2 4 2
7

Ieșire așteptată

Fii: niciunul
Descendenti: niciunul
Ascendenti: 4 1 3

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

descendentii-unui-nod.cpp
/*
 * Titlu: Fiii, descendenții și ascendenții unui nod
 * Clasa: 11
 * Capitol: Arbori
 * Descriere: Arborele este dat prin vectorul de tați (t[rădăcină] = 0). Fiii lui x sunt
 *            nodurile i cu t[i] = x. Un nod y este descendent al lui x dacă, urcând din y din
 *            tată în tată, ajungem în x. Ascendenții lui x sunt nodurile întâlnite urcând din
 *            x până la rădăcină: tatăl, bunicul etc. Se afișează fiii și descendenții în ordine
 *            crescătoare, iar ascendenții de la tată spre rădăcină („niciunul” dacă nu există).
 * Complexitate: O(n · h), unde h este înălțimea arborelui
 *
 * Exemplu
 * Intrare:
 * 8
 * 3 3 0 1 1 2 4 2
 * 1
 * Ieșire:
 * Fii: 4 5
 * Descendenti: 4 5 7
 * Ascendenti: 3
 *
 * Exemplu
 * Intrare:
 * 8
 * 3 3 0 1 1 2 4 2
 * 7
 * Ieșire:
 * Fii: niciunul
 * Descendenti: niciunul
 * Ascendenti: 4 1 3
 */
#include <iostream>
using namespace std;

int t[100005];

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
    }
    cin >> x;

    bool exista = false;
    cout << "Fii:";
    for (int i = 1; i <= n; i++)
    {
        if (t[i] == x)
        {
            cout << ' ' << i;
            exista = true;
        }
    }
    cout << (exista ? "" : " niciunul") << '\n';

    exista = false;
    cout << "Descendenti:";
    for (int i = 1; i <= n; i++)
    {
        if (i == x)
        {
            continue;
        }
        int y = t[i];
        while (y != 0 && y != x)
        {
            y = t[y];
        }
        if (y == x)
        {
            cout << ' ' << i;
            exista = true;
        }
    }
    cout << (exista ? "" : " niciunul") << '\n';

    cout << "Ascendenti:";
    if (t[x] == 0)
    {
        cout << " niciunul";
    }
    for (int y = t[x]; y != 0; y = t[y])
    {
        cout << ' ' << y;
    }
    cout << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.