注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

在路上...

点滴感悟,成长记录...

 
 
 

日志

 
 

【Practice】递归法和非递归法实现三种遍历二叉树方法  

2012-02-13 22:05:49|  分类: Practice |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

二叉树的遍历问题很重要,一般按照从左到右的顺序分为三种,即前序遍历、中序遍历和后序遍历。而根据采用的具体实现方法又分为递归法和非递归法。递归法很容易实现,非递归法需要借助于栈来辅助存储一些中间节点,除了后序遍历比较复杂以外,其他两种也较为容易理解。本代码中使用的是顺序容器适配器-stack,在使用时要包含<stack>头文件。

树结构如下:

【Practice】递归法和非递归法实现三种遍历二叉树方法 - 紫玄客 - 在路上...

闲话少说,上代码:

//前序遍历二叉树(递归法)
void preOrder(TNode *root)
{
 if (root!=NULL)
 {
  cout<<root->val<<" ";
  preOrder(root->pl);
  preOrder(root->pr);
 }

}
//前序遍历二叉树(非递归法)
void preOrder_noRec(TNode *root)
{
 stack<TNode*> sp;
 while(root!=NULL||!sp.empty())
 {
  if (root!=NULL)
  {
   cout<<root->val<<" ";
   sp.push(root);
   root = root->pl;
  }
  else
  {
   root = sp.top();
   sp.pop();
   root = root->pr;
  }
 }
}

//中序遍历二叉树(递归法)
void inOrder(TNode *root)
{
 if (root!=NULL)
 {
  inOrder(root->pl);
  cout<<root->val<<" ";
  inOrder(root->pr);
 }
}
//中序遍历二叉树(非递归法)
void inOrder_noRec(TNode *root)
{
 stack<TNode*> sp;
 while(root!=NULL||!sp.empty())
 {
  if (root!=NULL)
  {
   sp.push(root);
   root = root->pl;
  }
  else
  {
   root = sp.top();
   sp.pop();
   cout<<root->val<<" ";
   root = root->pr;
   
  }

 }
}
//后序遍历二叉树(递归法)
void postOrder(TNode *root)
{
 if (root!=NULL)
 {
  postOrder(root->pl);
  postOrder(root->pr);
  cout<<root->val<<" ";
 }
}
//后序遍历二叉树(非递归法)
void postOrder_noRec(TNode *root)
{
 stack<TNode*> sp;
 TNode *pre = NULL;
 while(root!=NULL||!sp.empty())
 {
  if (root!=NULL)
  {
   sp.push(root);
   root = root->pl;
  }
  else
  {
   root = sp.top();
   if(root->pr!=NULL&&pre!=root->pr)
   {
    root = root->pr;
   }
   else
   {
    root = pre = sp.top();
    cout<<root->val<<" ";
    sp.pop();
    root = NULL;
   }

  }

 }
}

运行结果:
【Practice】递归法和非递归法实现三种遍历二叉树方法 - 紫玄客 - 在路上...
 

  评论这张
 
阅读(302)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017