Прежде всего, я предполагаю, что у ваших узлов есть «родительское» поле, которое указывает на их родителя.Это либо так, либо вам нужен стек, чтобы иметь возможность перемещаться обратно вверх по дереву (и, следовательно, не может достичь этого требования O (1) вспомогательной памяти).
Существует хорошо известныйитерация порядка, которая является итерационной и в пространстве O (1).Предположим, например, что вы хотите напечатать элементы по порядку.По сути, когда вы проходите бинарное дерево, вы должны в любой момент, в любом данном узле, решить, хотите ли вы переместиться вверх (к родителю), влево (к левому потомку) или вправо.Идея этого алгоритма состоит в том, чтобы основывать это решение на том, откуда вы пришли:
- , если вы выходите из родительского узла, тогда вы явно посещаете узел в первый раз, поэтому вы идете ВЛЕВО;
- если вы пришли от левого потомка, то вы посетили все узлы, которые меньше текущего узла, поэтому вы можете напечатать (помните, что мы хотим напечатать узлы по порядку здесь) текущий узел, а затемgo RIGHT;
- наконец, если вы пришли от правильного дочернего элемента, это означает, что вы посетили все поддерево с корнем в этом конкретном узле, и поэтому вы можете вернуться к родительскому элементу.
ОК: это алгоритм, который вы берете за основу.Теперь, разумеется, если вы деструктивно модифицируете это в связанный список, вам следует изменить узел, только если вы больше не собираетесь его посещать.Это когда вы подходите справа.В этот момент вы должны решить, каким будет преемник этого узла ...?
Что ж, вам нужно постоянно отслеживать два указателя: один на самый маленький узел, который выпосетил, и один к самому большому узлу, который вы посетили в текущем корневом поддереве.Вы используете наименьшее в качестве преемника для узлов, которые вы в последний раз посещаете, когда вы подходите от правильного дочернего элемента, и используете наибольшее в качестве преемника для узлов, которые вы в последний раз посещаете, приходящих откуда-то еще, потому что у них нет правильного дочернего элемента!
РЕДАКТИРОВАТЬ 1 : я забыл сказать, что неявно считаю, что поле «родитель» в двоичном дереве становится полем «следующий» в связанном списке - это то, что я изменяюна последнем шаге.
РЕДАКТИРОВАТЬ 3 : следующая часть моего ответа оказалась не совсем ответить на исходный вопрос (но то, что предшествует все еще уместно).
РЕДАКТИРОВАТЬ 2 : Следуя понятному желанию Сванте, я высказал свое предложение об использовании левых вращений в некотором коде:
#include <stdlib.h>
#include <stdio.h>
typedef struct node *node;
struct node
{
int value;
node left;
node right;
};
node new_node(int value, node left, node right)
{
node n = (node) malloc(sizeof(struct node));
n->value = value; n->left = left; n->right = right;
return n;
}
int rotate_right(node tree)
{
if(tree != NULL && tree->left != NULL)
{
node
a = tree->left->left,
b = tree->left->right,
c = tree->right;
int tmp = tree->value;
tree->value = tree->left->value;
tree->left->value = tmp;
tree->left->left = b;
tree->left->right = c;
tree->right = tree->left;
tree->left = a;
return 1;
}
return 0;
}
Функция поворота не изящна, но таковалегко запутаться, я попытался следовать тому же наименованию, которое использовалось в статье Википедии о вращениях .Узлы A, B, C названы так в моем коде;узлы P и Q - нет, и поскольку я решил не использовать указатели указателей, я вместо этого прибегнул к хитрости переключения значений P и Q --- в вместо мест переключения.Имея в своем распоряжении «вращение_право», алгоритм преобразования довольно прост:
void convert_to_list(node tree)
{
if(tree != NULL) {
while(rotate_right(tree) != 0);
convert_to_list(tree->right);
}
}
Полученное дерево является отсортированным связанным списком, где указатель списка следующий используетсябыть указателем вправо в дереве.Наконец, вот тестовая программа:
int main()
{
node t =
new_node(4,
new_node(2, NULL, new_node(3, NULL, NULL)),
new_node(8, new_node(5, NULL, NULL), NULL));
convert_to_list(t);
for(; t != NULL; t = t->right)
printf("%d, ", t->value);
return 0;
}