Это возможно, если у вас есть ссылка на родителя в каждом потомке. Когда вы столкнетесь с ребенком, посетите левое поддерево. Когда вернетесь, проверьте, не являетесь ли вы левым ребенком своего родителя. Если это так, посетите правое поддерево. В противном случае продолжайте идти вверх, пока не станете левым дочерним элементом или пока не достигнете корня дерева.
В этом примере размер стека остается постоянным, поэтому дополнительная память не используется. Конечно, как указал Мердад, ссылки на родителей можно рассматривать как пространство 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) для доступа в любом порядке к элементам дерева, не требуя от дочерних элементов родительских ссылок или изменяя структуру дерева.
person
Kyle Cronin
schedule
26.04.2009
