프로 그래 밍 의 아름다움 3.10 레이 어 링 이 진 트 리 옮 겨 다 니 기
2721 단어 프로 그래 밍 의 아름다움
이것 은 확장 문제 에 대해 비교적 잘 하지만,창고 로 실현 하 는 것 을 고려 할 수 있다http://blog.csdn.net/houhouzhe/article/details/6546950
두 문제
1.두 갈래 나 무 를 층 으로 나 누 어 옮 겨 다 닌 다.
2.특정한 차원 의 노드 를 인쇄 합 니 다(그 중 뿌리 노드 는 0 층 입 니 다)
#include <iostream>
#include<vector>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
};
//max{d(u1,v1),...d(uk,vk),max1+max2+2}
void build(Node *&root){
Node *t1 = new Node();
t1->data = 1;
Node *t2 = new Node();
t2->data = 2;
Node *t3 = new Node();
t3->data = 3;
Node *t4 = new Node();
t4->data = 4;
Node *t5 = new Node();
t5->data = 5;
Node *t6 = new Node();
t6->data = 6;
Node *t7 = new Node();
t7->data = 7;
Node *t8 = new Node();
t8->data = 8;
Node *t9 = new Node();
t9->data = 9;
t1->left = t2;
t1->right = t3;
t2->left = t4;
t2->right = t5;
t4->left = t6;
t4->right = t7;
t6->left = t8;
t6->right = NULL;
t7->left = NULL;
t7->right = t9;
t3->left = NULL;
t3->right = NULL;
t5->left = NULL;
t5->right = NULL;
t8->left = NULL;
t8->right = NULL;
t9->left = NULL;
t9->right = NULL;
root = t1;
}
void prints(Node *root){
if(root==NULL)return;
if(root->left)prints(root->left);
if(root->right)prints(root->right);
cout<<root->data<<" ";
}
int max(int a,int b){
return a>b?a:b;
}
void PrintNodeAtLevel1(Node *root,int level){
if(level==0){
if(root!=NULL){
cout<<root->data<<" ";
return;
}
else
return;
}
if(root==NULL)return;
PrintNodeAtLevel1(root->left,level-1);
PrintNodeAtLevel1(root->right,level-1);
}
int PrintNodeAtLevel(Node *root,int level){//
if(!root||level<0){
return 0;
}
if(level==0){
cout<<root->data<<" ";
return 1;
}
return PrintNodeAtLevel(root->left,level-1)+PrintNodeAtLevel(root->right,level-1);
}
void Printall(Node *root){
for(int i=0;i<5;i++){
PrintNodeAtLevel(root,i);
cout<<endl;
}
}
void PrintNodeByLevel(Node *root){
if(root==NULL)return;
vector<Node*> vec;
vec.push_back(root);
int cur = 0;
int last = 1;
while(cur<vec.size()){
last = vec.size();
while(cur<last){
cout<<vec[cur]->data<<" ";
if(vec[cur]->left){
vec.push_back(vec[cur]->left);
}
if(vec[cur]->right){
vec.push_back(vec[cur]->right);
}
cur++;
}
}
}
int main(){
Node *root;
build(root);
prints(root);
cout<<endl;
//cout<<PrintNodeAtLevel(root,1);
//Printall(root);
PrintNodeByLevel(root);
return 0;
}