从上往下打印二叉树

题目

　　从上往下打印出二叉树的每个节点，同层节点从左至右打印

思路

　　如何广度优先遍历一个有向图？同样也是基于队列实现，树是图的一种特殊退化形式，从上向下打印二叉树，本质就是广度优先遍历，考察通常借助使用一个队列或一个栈来完成。

1. 队列：要求每层数据从左到右保存则用队列
2. 栈：要求每层数据从右到左保存则用栈（这种要求一般出现在“之”字型遍历 二叉树的题上）

拓展

　　广度优先遍历需要用到队列

1. 首先把起始结点（对于树来说是根结点）放入队列
2. 接下来每次从队列的队首取一个结点，遍历这个节点之后把他能到达的结点（对树来说是子节点）依次放入队列
3. 重复这个过程，知道队列中的结点被全部遍历

#include <iostream>
#include <queue>
using namespace std;

struct tree
{
    double data;
    struct tree *left,*right;
    tree(int d=0):data(d)
    {
        left=right=nullptr;
    }
};
class Solution
{
    public:
        void create(tree *&root);
        void pre_order(tree *root);//中序遍历
        void print_from_top_to_bottom(tree *root);
        tree *root;    
};
void Solution::create(tree *&root)
{
    double x;
    cin>>x;
    if(x==0)
        root=nullptr;
    else
    {
        root=new tree();
        root->data=x;
        create(root->left);
        create(root->right);
    }
}
void Solution::pre_order(tree *root)
{
    if(root)
    {
        cout<<root->data<<endl;
        pre_order(root->left);
        pre_order(root->right);
    }
}
void Solution::print_from_top_to_bottom(tree *root)
{
    if(!root)
        return;
    deque<tree *> q;
 
    q.push_back(root);
    while(q.size())
    {
        auto t=q.front();
        q.pop_front();
        
        cout<<t->data<<endl;
        
        if(t->left)
            q.push_back(t->left);
        if(t->right)
            q.push_back(t->right);
    }
}
int main()
{
    Solution s;
    s.create(s.root);
    //s.pre_order(s.root);
    s.print_from_top_to_bottom(s.root);
    return 0;
}