Пересеките дерево без рекурсии и стека в C
Как пересечь каждый узел дерева эффективно без рекурсии в C (никакой C++)?
Предположим, что у меня есть следующая структура узла того дерева:
struct Node
{
struct Node* next; /* sibling node linked list */
struct Node* parent; /* parent of current node */
struct Node* child; /* first child node */
}
- Это не домашняя работа.
- Я предпочитаю глубину сначала.
- Я не предпочитаю дополнительной необходимой структуры данных (такой как стек).
- Я предпочитаю самый эффективный путь с точки зрения скорости (не, располагают с интервалами).
- Можно изменить или добавить члена
Nodeструктура, чтобы хранить дополнительную информацию.
5 ответов
Если вы не хотите ничего хранить и у вас все в порядке с поиском в глубину:
process = TRUE;
while(pNode != null) {
if(process) {
//stuff
}
if(pNode->child != null && process) {
pNode = pNode->child;
process = true;
} else if(pNode->next != null) {
pNode = pNode->next;
process = true;
} else {
pNode = pNode->parent;
process = false;
}
}
Будет проходить по дереву; Процесс предназначен для предотвращения повторного попадания в родительские узлы при обратном перемещении вверх.
Вам нужно будет сохранить его в повторяющемся списке. будет работать базовый список с индексами. Затем вы просто переходите от 0 к концу просмотра данных.
Если вы хотите избежать рекурсии, вам нужно удерживать ссылку на каждый объект в дереве.
Вы можете использовать метод Pointer Reversal. Недостатком является то, что вам нужно сохранить некоторую информацию внутри узла, поэтому его нельзя использовать на const структуре данных.
Это похоже на упражнение, которое я выполнял в инженерной школе 25 лет назад. Я думаю, что это называется алгоритмом конверта дерева, поскольку он строит конверт дерева.
Не могу поверить, что это так просто. Должно быть, я где-то сделал незаметную ошибку. Независимо от любой ошибки, я считаю, что стратегия охвата верна. Если код ошибочный, просто рассматривайте его как псевдокод.
while current node exists{
go down all the way until a leaf is reached;
set current node = leaf node;
visit the node (do whatever needs to be done with the node);
get the next sibling to the current node;
if no node next to the current{
ascend the parentage trail until a higher parent has a next sibling;
}
set current node = found sibling node;
}
Код:
void traverse(Node* node){
while(node!=null){
while (node->child!=null){
node = node->child;
}
visit(node);
node = getNextParent(Node* node);
}
}
/* ascend until reaches a non-null uncle or
* grand-uncle or ... grand-grand...uncle
*/
Node* getNextParent(Node* node){
/* See if a next node exists
* Otherwise, find a parentage node
* that has a next node
*/
while(node->next==null){
node = node->parent;
/* parent node is null means
* tree traversal is completed
*/
if (node==null)
break;
}
node = node->next;
return node;
}
Обычно вы используете собственную структуру данных stack, которая хранит список узлов (или очередь, если вам нужен обход по порядку уровней).
Вы начинаете с того, что помещаете любой заданный начальный узел в стек. Затем вы входите в свой основной цикл, который продолжается до тех пор, пока стек не станет пустым. После того, как вы выталкиваете каждый узел из стека, вы выталкиваете его следующий и дочерние узлы, если они не пусты.