parcours de l'arborescence des niveaux sans utiliser de mémoire supplémentaire

Une façon pourrait être d'utiliser les pointeurs frères de droite qui sont nuls, pour rendre tous les nœuds frères les uns des autres (temporairement).

Vous pouvez utiliser un pointeur lent et rapide. Le rapide serait toujours au dernier frère (qui a un pointeur nul comme frère droit ). Le pointeur left-child du nœud lent serait alors copié dans ce right-frère , après quoi le pointeur rapide se poursuivrait à nouveau vers la fin. Le pointeur lent va d'un pas vers la droite et répète les mêmes. Lorsque le pointeur lent atteint également la fin, tous les nœuds seront frères et sœurs. Le pointeur lent ou rapide peut être utilisé pour afficher les valeurs dans l'ordre des niveaux. Cela fera le travail, mais l'arbre aura été détruit en conséquence.

Pour restaurer l'arbre, je suggérerais que pendant le processus ci-dessus, la direction de tous les bords frères soit inversée. Cela signifie que vous devez avoir un autre pointeur qui se trouve derrière le pointeur lent. Cela permettra d'effectuer l'inversion entre ces deux. C'est un peu obscur, car le frère droit pointera alors en fait vers quelque chose qui est principalement un frère gauche .

Après le processus ci-dessus , les pointeurs seront à la fin de la liste des nœuds, mais comme nous avons inversé les bords frères, nous pouvons également revenir en arrière et inverser à nouveau les bords. Une difficulté est de savoir quels pointeurs frères devraient redevenir nuls (quand un nœud était à l'origine un enfant le plus à droite). Cela peut être fait en ayant à nouveau un pointeur rapide se déplaçant vers l'avant (dans la direction gauche) pour trouver les nœuds qui ont un enfant. Si le pointeur qui est en retard sur le pointeur lent atteint un tel enfant, nous savons que le nœud du pointeur lent devrait avoir un pointeur nul comme frère droit . Lorsque ce correctif est appliqué, le pointeur rapide devrait à nouveau courir pour trouver un autre nœud parent, ... etc.

Notez que les pointeurs left-child ne sont pas modifiés par cet algorithme.

Donc, au total, cette solution utilise trois pointeurs et la structure de l'arbre lui-même.

Voici un exemple d'arbre que j'ai utilisé dans une implémentation ci-dessous: p >

void printTree(Node node, int indent) {
    if (!node) return;
    for (int i = 0; i < indent; i++) printf("  ");
    printf("%d\n", node->data);
    printTree(node->leftChild, indent+1);
    printTree(node->rightSibling, indent);
}

Implémentation en JavaScript - extrait exécutable:

#include <stdio.h>
#include <stdlib.h>

// define Node as a pointer to a node struct
typedef struct node {
    int data;
    struct node *leftChild;
    struct node *rightSibling;
} * Node;

// Some helper functions to ease the creation of a tree:
Node sibling(Node leftSibling, Node rightSibling) {
    leftSibling->rightSibling = rightSibling;
    return leftSibling;
}

Node parent(Node parent, Node child) {
    parent->leftChild = child;
    return parent;
}

Node create(int data) {
    Node node = malloc(sizeof(struct node));
    node->data = data;
    return node;
}
// end - helper functions

void traverse(Node node) {
    Node lead = node; // ...walks somewhere ahead of node
    Node lag = NULL; // ... always follows one step behind node
    while (node) {
        printf("%d\n", node->data); // output
        lead->rightSibling = node->leftChild;
        while (lead->rightSibling) lead = lead->rightSibling;
        // rotate: point node to next right-sibling, and reverse direction of sibling edge
        Node temp = node->rightSibling;
        node->rightSibling = lag;
        lag = node;
        node = temp;
    }

    // Restore tree
    lead = node = lag->rightSibling; // backwards
    lag->rightSibling = NULL;
    while (lead != NULL && lead->leftChild == NULL) lead = lead->rightSibling; // actually going left!
    while (node != NULL) {
        if (lead != NULL && lead->leftChild == lag) {
            // When lag is the leftChild of some node (lead), then lag should not be the target of a rightSibling
            lag = node;
            node = node->rightSibling;
            lag->rightSibling = NULL;
            // Find previous parent
            lead = lead->rightSibling;
            while (lead != NULL && lead->leftChild == NULL) lead = lead->rightSibling; // actually going left!
        } else {
            // walk back and restore sibling pointers
            Node temp = node->rightSibling;
            node->rightSibling = lag;
            lag = node;
            node = temp;
        }
    }
}

int main(void) {
    // Create the example tree
    Node root = parent(create(1), 
        sibling(parent(create(2), 
            sibling(create(5), sibling(parent(create(6),
                sibling(create(14), sibling(create(15), create(16)))
            ), create(7)))
        ), sibling(parent(create(3),
            sibling(create(8), create(9))
        ), parent(create(4),
            sibling(create(10), sibling(parent(create(11),
                sibling(create(17), sibling(create(18), create(19)))
            ), sibling(create(12), create(13))))
        )))
    );
    traverse(root);
    return 0;
}

Version en C

Je ne parle pas couramment le C, mais je pense que cela devrait le faire:

function * traverse(node) {
    let lead = node; // ...walks somewhere ahead of node
    let lag = null; // ... always follows one step behind node
    while (node) {
        yield node.data; // output
        lead.rightSibling = node.leftChild;
        while (lead.rightSibling) lead = lead.rightSibling;
        // rotate: point node to next right-sibling, and reverse direction of sibling edge
        [node.rightSibling, lag, node] = [lag, node, node.rightSibling]
    }
    
    // Restore tree
    lead = node = lag.rightSibling; // backwards
    lag.rightSibling = null;
    while (lead !== null && lead.leftChild === null) lead = lead.rightSibling; // actually going left!
    while (node) {
        if (lead !== null && lead.leftChild === lag) {
            // When lag is the leftChild of some node (lead), then lag should not be the target of a rightSibling
            [node.rightSibling, lag, node] = [null, node, node.rightSibling];
            // Find previous parent
            lead = lead.rightSibling;
            while (lead !== null && lead.leftChild === null) lead = lead.rightSibling; // actually going left!
        } else {
            // walk back and restore sibling pointers
            [node.rightSibling, lag, node] = [lag, node, node.rightSibling];
        }
    }
}

// Create node, given its data and child nodes
function Node(data, ...children) {
    // Link the children as siblings
    if (children.length > 1) children.reduceRight((a, b) => (b.rightSibling = a, b))
    // Create the node itself. For now, without any siblings
    return {
        data,
        leftChild: children.length ? children[0] : null,
        rightSibling: null
    };
}

// Example tree
let tree = Node(1, 
    Node(2, 
        Node(5), Node(6,
            Node(14), Node(15), Node(16)
        ), Node(7)
    ), Node(3,
        Node(8), Node(9)
    ), Node(4,
        Node(10), Node(11,
            Node(17), Node(18), Node(19)
        ), Node(12), Node(13)
    )
);

// Apply the algorithm and output the yielded values     
console.log(...traverse(tree)); 

Pour imprimer l'arborescence dans un format très basique, vous pouvez utiliser cette fonction:

          1
         /
        2 ------------ 3 ---------4
       /              /          /
      5 -- 6 -- 7    8 -- 9     10 -- 11 -- 12 -- 13
          /                           /
        14 -- 15 -- 16              17 -- 18 -- 19

Cela aidera à vérifier qu'en effet l'arbre est le même avant et après le parcours. p >