Это возможно, если у вас есть ссылка на родителя у каждого ребенка. Когда вы встретите ребенка, посетите левое поддерево. При возвращении проверьте, не является ли вы левым потомком своего родителя. Если так, посетите правильное поддерево. В противном случае продолжайте идти вверх, пока вы не оставите ребенка или пока не достигнете корня дерева.
В этом примере размер стека остается постоянным, поэтому дополнительная память не используется. Конечно, как отметил Мерад, ссылки на родителей можно рассматривать как пространство O (n), но это скорее свойство дерева, чем свойство алгоритма.
Если вас не волнует порядок, в котором вы проходите дерево, вы можете назначить интегральное отображение для узлов, где корень равен 1, потомки корня равны 2 и 3, потомки тех 4 , 5, 6, 7 и т. Д. Затем вы перебираете каждую строку дерева, увеличивая счетчик и получая доступ к этому узлу по его числовому значению. Вы можете отслеживать максимально возможный дочерний элемент и останавливать цикл, когда ваш счетчик пропустит его. По времени это крайне неэффективный алгоритм, но я думаю, что он занимает O (1) пробела.
(Я позаимствовал идею нумерации из кучи. Если у вас есть узел N, вы можете найти детей в 2N и 2N + 1. Вы можете работать в обратном направлении от этого номера, чтобы найти родителя ребенка.)
Вот пример этого алгоритма в действии на C. Обратите внимание, что нет malloc'ов, кроме создания дерева, и что нет рекурсивных функций, что означает, что стек занимает постоянное пространство:
#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);
}
Я прошу прощения за качество кода - это в значительной степени подтверждение концепции. Кроме того, время выполнения этого алгоритма не является идеальным, поскольку он выполняет большую работу, чтобы компенсировать неспособность поддерживать какую-либо информацию о состоянии. С положительной стороны, это соответствует требованиям алгоритма пространства O (1) для доступа в любом порядке к элементам дерева, не требуя дочерних родительских ссылок или изменения структуры дерева.