題目
題目1523：從上往下打印二叉樹時間限制：1 秒
內存限制：128 兆
特殊判題：否
提交：18
解決：3
題目描述：
從上往下打印出二叉樹的每個節點，同層節點從左至右打印。
輸入：
輸入可能包含多個測試樣例，輸入以EOF結束。
對於每個測試案例，輸入的第一行一個整數n(1<=n<=1000, ：n代表將要輸入的二叉樹元素的個數（節點從1開始編號）。接下來一行有n個數字,代表第i個二叉樹節點的元素的值。接下來有n行，每行有一個字母Ci。
Ci=’d’表示第i個節點有兩子孩子，緊接著是左孩子編號和右孩子編號。
Ci=’l’表示第i個節點有一個左孩子，緊接著是左孩子的編號。
Ci=’r’表示第i個節點有一個右孩子，緊接著是右孩子的編號。
Ci=’z’表示第i個節點沒有子孩子。
輸出：
對應每個測試案例，
按照從上之下，從左至右打印出二叉樹節點的值。
樣例輸入：
7
8 6 5 7 10 9 11
d 2 5
d 3 4
z
z
d 6 7
z
z
樣例輸出：
8 6 10 5 7 9 11
分析
可以用類似廣度優先搜索的方法
不同的是這裡用vector保存遍歷到的節點編號
在搜索到某個節點後，將該節點的子節點push_back到vector
代碼
[cpp]
include <iostream>
#include <vector>
#include <string>
struct Node{
int value;
int lid;
int rid;
};
std::vector<Node> vn;
std::vector<int> v; //保存訪問的節點編號
void Bsearch(){
v.push_back(1);
std::vector<int>::size_type vid = 0;;
while(vid!=v.size()){
int nodeId = v.at(vid)-1;//得到節點編號-1
std::cout<<vn.at(nodeId).value;
if(vn.at(nodeId).lid){
v.push_back(vn.at(nodeId).lid);
}
if(vn.at(nodeId).rid){
v.push_back(vn.at(nodeId).rid);
}
if(vid<v.size()-1)
std::cout<<" ";
else
std::cout<<std::endl;
vid++;
}
}
void judo(int n){
if(n==0){
std::cout<<"NULL"<<std::endl;
return;
}
Node nd;
nd.lid = 0;
nd.rid = 0;
for(int i = 0;i<n;i++){
std::cin>>nd.value;
vn.push_back(nd);
}
std::string ci;
for(int i = 0;i<n;i++){
std::cin>>ci;
switch (ci[0]){
case 'd':
std::cin>>vn.at(i).lid>>vn.at(i).rid;
break;
case 'r':
std::cin>>vn.at(i).rid;
break;
case 'l':
std::cin>>vn.at(i).lid;
break;
case 'z':
break;
}
}
Bsearch();
}
int main() {
int n;
while(std::cin>>n){
judo(n);
}
return 0;
}
#include <iostream>
#include <vector>
#include <string>
struct Node{
int value;
int lid;
int rid;
};
std::vector<Node> vn;
std::vector<int> v; //保存訪問的節點編號
void Bsearch(){
v.push_back(1);
std::vector<int>::size_type vid = 0;;
while(vid!=v.size()){
int nodeId = v.at(vid)-1;//得到節點編號-1
std::cout<<vn.at(nodeId).value;
if(vn.at(nodeId).lid){
v.push_back(vn.at(nodeId).lid);
}
if(vn.at(nodeId).rid){
v.push_back(vn.at(nodeId).rid);
}
if(vid<v.size()-1)
std::cout<<" ";
else
std::cout<<std::endl;
vid++;
}
}
void judo(int n){
if(n==0){
std::cout<<"NULL"<<std::endl;
return;
}
Node nd;
nd.lid = 0;
nd.rid = 0;
for(int i = 0;i<n;i++){
std::cin>>nd.value;
vn.push_back(nd);
}
std::string ci;
for(int i = 0;i<n;i++){
std::cin>>ci;
switch (ci[0]){
case 'd':
std::cin>>vn.at(i).lid>>vn.at(i).rid;
break;
case 'r':
std::cin>>vn.at(i).rid;
break;
case 'l':
std::cin>>vn.at(i).lid;
break;
case 'z':
break;
}
}
Bsearch();
}
int main() {
int n;
while(std::cin>>n){
judo(n);
}
return 0;
}
