Трассировка дерева без рекурсии и стека в C

Как эффективно перемещаться по каждому node дерева без рекурсии в C (нет С++)?

Предположим, что у меня есть следующая структура node этого дерева:

struct Node
{
    struct Node* next;   /* sibling node linked list */
    struct Node* parent; /* parent of current node   */
    struct Node* child;  /* first child node         */
}

Это не домашнее задание.
Сначала я предпочитаю глубину.
Я предпочитаю не создавать дополнительную структуру данных (например, стек).
Я предпочитаю наиболее эффективный способ с точки зрения скорости (а не пространства).
Вы можете изменить или добавить элемент структуры Node для хранения дополнительной информации.

Ответ 1

Если вы не хотите ничего хранить, и все в порядке с поиском глубины:

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;
    }
}

Проедет дерево; process заключается в том, чтобы удержать его от повторного попадания родительских узлов при его резервном копировании.

Ответ 2

Как правило, вы будете использовать собственную структуру данных стека, в которой хранится список узлов (или очередь, если вы хотите пройти обход уровня).

Вы начинаете с нажатия любого старта node на стек. Затем вы вводите свой основной цикл, который продолжается до тех пор, пока стек не будет пуст. После того, как вы поместите каждый node из стека, вы нажимаете на его следующий и дочерний узлы, если они не пусты.

Ответ 3

Вы можете использовать метод

Ответ 4

Это выглядит как упражнение, которое я сделал в инженерной школе 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;
}

Ответ 5

Вам нужно будет сохранить его в списке. будет работать базовый список с индексами. Затем вы просто переходите от 0 до конца, глядя на данные.

Если вы хотите избежать рекурсии, вам нужно удерживать ссылку на каждый объект внутри дерева.