Navigieren grundlegenden Binärbaum

Question

Also muss ich einen grundlegenden binären Baum für meine Anwendung erstellen, aber ich habe Probleme bei der Konzeption, wie man "navigiert", auch im Prozess der Generierung.

Jeder Knoten hat natürlich eine Adresse und führt zu zwei anderen Knoten, die jeweils einen positiven und einen negativen Wert enthalten. Meine Frage ist, wenn ich den Baum mit einer Schleife erstellen möchte, wie mache ich das? Bei der ersten Iteration gibt es zwei Knoten, bei der dritten wird es vier usw. - wie durchlaufe ich jede ihrer Adressen, bevor ich meine Schleife fortsetze?

for(int i=1;i<=5;i++){ 
     (*currentAddress).value = i; 
     (*currentAddress).positive = i; 
     (*currentAddress).negative = i*-1; 
     //update current address 
    } 

Muss ich BFS jede Iteration verwenden und halten nur Knoten hinzufügen, bis ich (2^n-1) Knoten erstellt haben?

Answer 1

Sie hätten eigentlich gerne linke und rechte Zeiger, oder? Und dann möchten Sie wahrscheinlich Rekursion verwenden. Zum Beispiel (in einigen randomish Sprache):

function Node* MakeNode(value, limit) { 
    Node* node = new Node(); 
    (*node).value = value; 
    // don't create any more children once we get to the depth limit. 
    if (value < limit) { 
     (*node).positive = MakeNode(value + 1); 
     (*node).negative = MakeNode(value - 1); 
    } 
    return node; 
} 

// create a 5 deep tree 
MakeNode(0, 5); 

Answer 2

So möchten Sie einen vollständigen binären Baum von einer bestimmten Tiefe unter Verwendung einer Schleife erstellen. Das ist möglich. Aber Sie sollten zuerst die Antwort von PaulColdrey in Betracht ziehen, da es ein bisschen einfacher ist.

Um einen Binärbaum iterativ zu erstellen, muss man wissen, dass sein jeder Knoten eindeutig mit einem Bitvektor identifiziert werden:

layer 0:      ___________________[0]___________________ 
           |           | 
layer 1:   ________[00]________      ________[10]________ 
        |     |      |     | 
layer 2:  ___[000]___   ___[100]___   ___[010]___   ___[110]___ 
      |   |  |   |   |   |  |   | 
layer 3: [0000]  [1000] [0100]  [1100] [0010]  [1010] [0110]  [1110] 

A Bit auf N-ten Position teilt den Zweig (links: 0/rechts: 1) wurde genommen, wenn von (N - 1) -te Schicht zu Nth gegangen wird. Mit anderen Worten, ein Bitvektor ist ein Pfad zu dem Knoten; siehe oben.

Es reicht aus, von 0 bis 2 ^K - 1 zu zählen, um alle möglichen Pfade zu Kth-Schichtknoten zu erhalten. Und darüber hinaus würde das N-te Bit beim Hochzählen niemals von 0 auf 1 wechseln, bis alle weniger signifikanten Bits von 0 auf 1 wechseln - was in diesem Fall bedeutet, dass der aktuelle N-te Schicht-Teilbaum voll ist.

Dies ermöglicht, nur einen aktuellen Knoten pro Layer zu speichern und alle untergeordneten Elemente neu zu erstellen, wenn sich ein übergeordneter Knoten ändert. Diese

ist, wie es aussieht, ist in C:

struct NODE { 
    struct NODE *side[2]; 
    double data; 
}; 

struct NODE *fulltree(int depth) { 
    struct NODE *curr[16] = {}; 
    int path, layer; 

    if ((depth >= 0) && (depth < 16)) { /** reject exceedingly large trees **/ 
     curr[0] = (struct NODE*)calloc(1, sizeof(struct NODE)); 
     for (path = 0; path < (1 << depth); ++path) 
      for (layer = 1; layer <= depth; ++layer) 
       if (((path^(path - 1)) >> (depth - layer)) & 1) { 
        curr[layer - 1]->side[(path >> (depth - layer)) & 1] = 
        curr[layer] = (struct NODE*)calloc(1, sizeof(struct NODE)); 
        curr[layer]->data = 
        ((path >> (layer - 1)) & 1)? layer : -layer; 
       } 
    } 
    return curr[0]; 
} 

Der Code geht davon aus, dass negative Zahlen auf dem Ziel-CPU sind two`s complement.