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

在路上...

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

 
 
 

日志

 
 

【Practice】分层遍历二叉树问题的两种解法  

2012-02-11 21:19:53|  分类: Practice |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

编程之美上的题目。

问题1:给定一棵二叉树,要求按分层遍历该二叉树,即从上到下按层次访问该二叉树(每一行将单输出一行),每一层要求访问的顺序为从左向右,并将节点依次编号。

问题2:写一个函数,打印二叉树中某层次的节点(从左向右),其中根结点为第1层。

解法1(递归法)

解决了问题2,问题1也就迎刃而解。问题2可以使用递归法进行,从根节点开始依据所给层数依次向下递归至所需层数为止。代码如下:

//二叉树的结构体表示

struct TNode
{
 
 TNode *pl;
 TNode *pr;
 int val;
 TNode():pl(NULL),pr(NULL),val(0){}
 TNode(int i):pl(NULL),pr(NULL),val(i){}
};

 

//创建一个二叉树

 TNode *treeNode1 = new TNode(1);
 TNode *treeNode2 = new TNode(2);
 TNode *treeNode3 = new TNode(3);
 TNode *treeNode4 = new TNode(4);
 TNode *treeNode5 = new TNode(5);
 TNode *treeNode6 = new TNode(6);
 TNode *treeNode7 = new TNode(7);
 TNode *treeNode8 = new TNode(8);
 treeNode1->pl = treeNode2;
 treeNode1->pr = treeNode3;
 treeNode2->pl = treeNode4;
 treeNode2->pr = treeNode5;
 treeNode3->pr = treeNode6;
 treeNode5->pl = treeNode7;
 treeNode5->pr = treeNode8;

 

//输出二叉树第level层的所有元素(递归法)
int printNodeAtLevel(TNode *tnode,int level)
{
 if (tnode==NULL || level<0)
 {
  return 0;
 }
 if (level == 1)
 {
  cout<<tnode->val<<" ";
  return 1;
 }
 return printNodeAtLevel(tnode->pl,level-1) + printNodeAtLevel(tnode->pr,level-1);
 
}

然后多次调用该函数,即可解决问题1.代码如下.这里很巧妙的一点就是不用求出该树的高度,而只需判断printNodeAtLevel函数的返回值即可,若返回0,则说明该层访问失败,也就是该层已经没有节点,已经达到了最大层数。

 //分层遍历二叉树(递归法)
 cout<<"分层遍历二叉树(递归法):"<<endl;

for (int level = 1; ;level++)
 {
  if (!printNodeAtLevel(treeNode1,level))
   break ;
  cout<<endl;
 }

解法2(迭代法)
使用这种方法来解决问题1.问题2仍可以使用递归法.本方法使用两个标准库容器队列分别存放当前节点和当前层数,并输出当前节点的值,然后根据当前节点和下一节点的层数是否相等来决定是否另起一行输出。具体代码如下:

 //分层遍历二叉树(迭代法)
 queue<TNode*> node;
 queue<int> level;
 node.push(treeNode1);
 level.push(1);
 int currentLevel = 1;
 cout<<"分层遍历二叉树(迭代法):"<<endl;
 while(!node.empty())
 {

  TNode *temp = node.front();
  node.pop();
  currentLevel = level.front();
  level.pop();
  if (temp->pl != NULL)
  {
   node.push(temp->pl);
   level.push(currentLevel+1);
  }
  if (temp->pr != NULL)
  {
   node.push(temp->pr);
   level.push(currentLevel+1);
  }
  cout<<temp->val<<" ";
  if (level.empty())
  {
   break;
  }
  if (currentLevel!=level.front())
  {
   cout<<endl;
  }
 }
 cout<<endl;


总结:递归法的效率较低,消耗更多的时间和空间。而且递归法需要每一次都从根节点开始访问每一层,这样以来效率更加下降。迭代法用队列作为辅助存储,不需要每一次都从根节点开始访问,提高了效率。
  评论这张
 
阅读(157)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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