更多名人名博

上市公司专栏

实时股价每分更新

纳斯达克(美元)(市值:亿美元)
综指: 涨跌幅:
公司 股价 涨幅度 市值
盛大
网易
九城
畅游
完美
巨人
新浪
百度
恒生指数(港币)(市值:亿港币)
综指: 涨跌幅:
公司 股价 涨幅度 市值
腾讯
金山
网龙
创业板
综指: 涨跌幅:
公司 股价 涨幅度 市值
宝网
d
您现在的位置:首页> 开发|游戏程序|专业工具| > 多叉树的递归遍历和堆栈遍历

多叉树的递归遍历和堆栈遍历

来源:IIEEG04-12-2011

//多叉树递归遍历

//假设树节点定义为:

struct Node{
   Node *pPNode;
   list childs;
};

//前序遍历(正序遍历):

void EnumNode(Node *pNode)
{

  do_something(pNode);

  list::iterator iter; //正向遍历器

  for(iter=pNode->childs.begin();iter!=pNode->childs.end();++iter)
  {
     EnumNode(*iter);
  }

}

//后序遍历(反序遍历):

void REnumNode(Node *pNode)
{

  list::reverse_iterator iter; //反向遍历器

  for(iter=pNode->childs.rbegin();iter!=pNode->childs.rend();++iter)
  {
     EnumNode(*iter);
  }

  do_something(pNode);

}

//多叉树堆栈遍历

//前序遍历(正序遍历):

void EnumNode(Node *pRoot)
{
  stack stack;
  stack.push(pRoot);
  Node *lpNode;

  while(!stack.empty())
  {
      lpNode = stack.top();
      stack.pop();

      do_something(lpNode);

      list::reverse_iterator iter; //反向遍历器

      for(iter=pNode->childs.rbegin();iter!=pNode->childs.rend();++iter)
      {
         stack.push(*iter);
      }
  }

}

//后序遍历(反序遍历):

void REnumNode(Node *pRoot)
{
  stack stack;
  stack.push(pRoot);
  Node *lpNode;
  Node *lpLastNode=NULL; //保存最近一次处理的节点,或者说某个节点的第一个子节点

  while(!stack.empty())
  {
      lpNode = stack.top();

      //lpLastNode!=*lpNode->childs.begin() //起关键性作用,防止再次进入已经处理过的节点
      if (lpNode->childs.size() && lpLastNode!=*lpNode->childs.begin())
      {

         list::iterator iter; //正向遍历器

         for(iter=pNode->childs.begin();iter!=pNode->childs.end();++iter)
         {
            stack.push(*iter);
         }

      }else{

         do_something(lpNode);

         lpLastNode=lpNode;
         stack.pop();

      }
  }

}

/*
关于后续遍历,程序流程是这样的:

1.从根出发
2.寻找含有子叶的节点
3.找到后,正序push到堆栈
4.取栈定节点,继续执行第2步
4.直到找到没有子叶的节点
5.开始处理,保存处理的节点指针
6.pop节点, Go Setp 2

注:以上代码非可直接运行代码,算法却清晰明了,稍加改动就可以使用。
*/