题目
从上往下打印出二叉树的每个结点,同一层的结点按照从左到右的顺序打印。例如输入下图中的二叉树,则依次打印出8、6、10、5、7、9、11
思路
与从上到下打印二叉树类似https://www.cnblogs.com/tianzeng/p/10186431.html,本题在定义两个变量,next_level表示下一层要打印的节点数 ,在遍历的如果有字结点,就执行next_level加一操作,be_printed表示本层剩余要打印的节点数,如果为0,表示已经打印完,可以打印下一层。
#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 print(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::print(tree *root) { if(!root) return; queue<tree *> q; q.push(root); int next_level=0;//下一层要打印的节点数 int be_printed=1;//本层要打印的节点数,开始只有一个根节点,初始化为1 while(!q.empty()) { auto t=q.front(); cout<<t->data<<" "; if(t->left) { q.push(t->left); ++next_level; } if(t->right) { q.push(t->right); ++next_level; } q.pop(); --be_printed; if(!be_printed) { cout<<endl; be_printed=next_level; next_level=0; } } } int main() { Solution s; s.create(s.root); s.print(s.root); return 0; }