Es ist möglich, wenn Sie in jedem Kind einen Link zu dem Elternteil haben. Wenn Sie auf ein Kind stoßen, besuchen Sie den linken Teilbaum. Wenn du zurückkommst, überprüfe, ob du das linke Kind deiner Eltern bist. Wenn ja, besuchen Sie den rechten Teilbaum. Andernfalls gehst du weiter, bis du das linke Kind bist oder bis du die Wurzel des Baumes triffst.
In diesem Beispiel wird die Größe des Stapels konstant bleibt, so gibt es keinen zusätzlichen Speicher verbraucht. Natürlich, wie Mehrdad darauf hingewiesen hat, können Links zu den Eltern als O (n) -Raum betrachtet werden, aber dies ist eher eine Eigenschaft des Baumes als eine Eigenschaft des Algorithmus.
Wenn Sie sich nicht um die Reihenfolge kümmern, in der Sie den Baum durchlaufen, können Sie den Knoten mit der Wurzel 1 eine integrale Zuordnung zuweisen, die Kinder der Wurzel sind 2 und 3, deren Kinder 4, 5, 6, 7, usw. Dann durchlaufen Sie jede Reihe des Baumes, indem Sie einen Zähler inkrementieren und auf diesen Knoten mit seinem numerischen Wert zugreifen. Sie können das höchstmögliche Kindelement verfolgen und die Schleife anhalten, wenn Ihr Zähler es passiert. Zeitlich ist dies ein extrem ineffizienter Algorithmus, aber ich denke, es braucht O (1) -Raum.
(lieh ich mir die Idee von Halden Nummerierung. Wenn Sie Knoten N haben, können Sie die Kinder bei 2N und 2N + 1 finden. Sie können von dieser Nummer arbeiten rückwärts, um die Eltern eines Kindes zu finden.)
Hier ist ein Beispiel dieses Algorithmus in Aktion in C. Beachten Sie, dass es keine malloc ist außer für die Schaffung des Baumes ist, und dass es keine rekursiven Funktionen, was bedeutet, dass der Stapel konstant Platz in Anspruch nimmt:
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
int value;
struct tree *left, *right;
} tree;
tree *maketree(int value, tree *left, tree *right)
{
tree *ret = malloc(sizeof(tree));
ret->value = value;
ret->left = left;
ret->right = right;
return ret;
}
int nextstep(int current, int desired)
{
while (desired > 2*current+1)
desired /= 2;
return desired % 2;
}
tree *seek(tree *root, int desired)
{
int currentid; currentid = 1;
while (currentid != desired)
{
if (nextstep(currentid, desired))
if (root->right)
{
currentid = 2*currentid+1;
root = root->right;
}
else
return NULL;
else
if (root->left)
{
currentid = 2*currentid;
root = root->left;
}
else
return NULL;
}
return root;
}
void traverse(tree *root)
{
int counter; counter = 1; /* main loop counter */
/* next = maximum id of next child; if we pass this, we're done */
int next; next = 1;
tree *current;
while (next >= counter)
{
current = seek(root, counter);
if (current)
{
if (current->left || current->right)
next = 2*counter+1;
/* printing to show we've been here */
printf("%i\n", current->value);
}
counter++;
}
}
int main()
{
tree *root1 =
maketree(1, maketree(2, maketree(3, NULL, NULL),
maketree(4, NULL, NULL)),
maketree(5, maketree(6, NULL, NULL),
maketree(7, NULL, NULL)));
tree *root2 =
maketree(1, maketree(2, maketree(3,
maketree(4, NULL, NULL), NULL), NULL), NULL);
tree *root3 =
maketree(1, NULL, maketree(2, NULL, maketree(3, NULL,
maketree(4, NULL, NULL))));
printf("doing root1:\n");
traverse(root1);
printf("\ndoing root2:\n");
traverse(root2);
printf("\ndoing root3:\n");
traverse(root3);
}
Ich entschuldige mich für die Qualität des Codes - das ist weitgehend ein Beweis für das Konzept. Außerdem ist die Laufzeit dieses Algorithmus nicht ideal, da es viel Arbeit erfordert, um zu kompensieren, dass keine Zustandsinformationen aufrechterhalten werden können. Auf der positiven Seite passt dies jedoch zu der Rechnung eines O (1) -Raumalgorithmus für den Zugriff auf die Elemente des Baums in beliebiger Reihenfolge, ohne dass Kind-zu-Eltern-Verbindungen erforderlich sind oder die Struktur des Baums modifiziert wird.
Ich betrachte Link zu Eltern als O (n) Hilfsraum. Sie sollten Ihre Frage bearbeiten, um explizit zu erwähnen, dass Ihr Binärbaum keine solche Eigenschaft besitzt. –
Wie können Sie keine Zeiger auf Ihre übergeordneten Knoten haben? Wie kannst du ohne sie überhaupt über deinen Baum iterieren? ist das, wo der Stapel hereinkommt? Sie werden Elternzeiger sowieso brauchen, um auszubalancieren. –