C语言中无递归遍历树与栈

如果您不想存储任何内容,并且可以进行深度优先搜索:

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 是为了防止它在返回时重新命中父节点。

一般来说,您将使用自己的堆栈数据结构来存储节点列表(如果您需要级别顺序遍历,则使用队列)。

首先将任何给定的起始节点推到堆栈上。然后进入主循环,直到堆栈为空为止。从堆栈中弹出每个节点后,如果不是空的,则推送下一个节点和子节点。

这看起来像我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;
}

Pointer Reversal 方法。缺点是您需要在节点内保存一些信息,这样就不能在服务器上使用 const 数据结构。

如果要避免递归,需要保留树中每个对象的引用。