Обход дерева без рекурсии и стека в C - PullRequest
Новая
       33

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

11 голосов
/ 09 июля 2010

Как эффективно обойти каждый узел дерева без рекурсии в 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 struct для хранения дополнительной информации.

Ответы [ 5 ]

20 голосов
/ 09 июля 2010

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

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 должен предотвратить повторное попадание в родительские узлы при возврате.

8 голосов
/ 09 июля 2010

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

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

2 голосов
/ 10 июля 2010

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

Вы можете использовать метод обращения указателей . Недостатком является то, что вам необходимо сохранить некоторую информацию внутри узла, чтобы ее нельзя было использовать в const структуре данных.

0 голосов
/ 09 июля 2010

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

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

...