层序打印树

(晚上写这个停不下来啊。。赶紧写完不然回不了宿舍咯)

层序打印

题目的意思大家都懂吧,平时我们前序遍历,中序遍历,后续遍历的话用递归很容易搞定,但是这个问题啊,一用递归貌似就GG了(只是我想不出来),因为用递归的话,会向深度发展(我感觉),所以只能另找一条路了。

这种方法必须是,每次只走一步,不要一次性走到底的!
上哪里去找这么听话的。。呢?

跟上篇文章一样
栈模拟递归
这里我们也使用一个队列来存储所经过的节点,上次没有深入的思考,其实手动的用队列去存储经过的节点话,每次只执行一次的!

也就是说,这样既能简单的遍历树,并且每次还只往下走一步!

太完美了!

所以呢,跟上次一样,我们存储经过的路径,只不过这里我们需要一个先进先出的容器,我们选择了队列,路线就是:push->print->pop

下面是代码:

void printTreeTopDown(treeNode* tree)
{
    if (!tree)
        return;
    std::deque<treeNode*> nodeDeque;
    nodeDeque.push_back(tree);
    while (nodeDeque.size())
    {
        treeNode* tmp = nodeDeque.front();
        nodeDeque.pop_front();
        std::cout << tmp->data << " ";

        if (tree->left)
            nodeDeque.push_back(tree->left);
        if (tree->right)
            nodeDeque.push_back(tree->right);
    }
}

(我并没有去测试代码,所以不知道有没有bug。。,欢迎指出)
文章参考何海涛大神文章

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 10,621评论 0 12
  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 9,946评论 1 31
  • 基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平...
    yhthu阅读 9,813评论 1 5
  • 什么是二叉树? 引用自百度百科:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(...
    AnICoo1阅读 5,198评论 0 1
  • 今天早上起床后没有同洋洋聊天,直接去楼下吃饭了,吃完饭后他姨带他去村里的上面那排屋拨莲子,过了半个小时左右,我也上...
    王翠英阅读 1,594评论 0 0

友情链接更多精彩内容