알고리즘 문제16: 이원 트리를 입력하여 위에서 아래로 층별로 트리의 각 결점을 인쇄하고 같은 층에서 왼쪽에서 오른쪽으로 순서대로 인쇄한다

제목(Microsoft): 2원 트리를 입력하고 위에서 아래로 트리의 각 결점을 층별로 인쇄하며 같은 층에서 왼쪽에서 오른쪽으로 순서대로 인쇄합니다.예를 들어 8/\6 10/\/\5 7 9 11 출력 86 10 5 7 9 11을 입력합니다.
-----------------------------------
여전히 두 갈래 나무다. 그것이 바로 훑어보는 문제다. 자, 이곳을 훑어보는 것은 우리가 이전의 훑어보는 방식이 아닌 것 같다. 만약에 그 순서에 따라 깊이를 우선하는 훑어보는 방식이다. 여기서 더 바라는 것은 넓이로 인쇄하는 것이다. 물론 여기는 저장 메커니즘을 빌려야 한다. 물론 체인 시계이기도 하다. 생각해 보면 체인 시계에 먼저 들어간 요소는 층수보다 높고 인쇄되어야 한다.그리고 그것의 하층부를 합류시키는 것으로 유추하다
드디어 이 문제는 오랫동안 쓰지 못한 데이터 구조---대열!!
자, 여기 보시면 답을 얻을 수 있을 거예요.
다음은 이 문제의 답안을 제시하는 동시에 하중서 인쇄를 연습했습니다. 물론 간단하지만...
여러분 스스로 대기열을 작성해서 알고리즘을 연습할 때 라이브러리의 Queue를 최대한 적게 사용하시기 바랍니다.

//============================================================================
// Name        : PrintBT.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

/*
 *  
 */
struct Node{
	int value;
	Node* left;
	Node* right;
};

/*
 *  
 */
struct QueueNode{
	Node* node;
	QueueNode* next;
};

void addNode(Node* &p, int value);
void printBT(Node* p);
void printBTByFloor();

QueueNode* containerHead = NULL;
QueueNode* containerCur = NULL;

int main() {

	Node* head = NULL;
	int input = 0;
	while(true){
		cin>>input;
		if(input != -1)
			addNode(head, input);
		else
			break;
	}

	printBT(head);
	cout<<endl;
	// 
	if(head){
		containerHead = new QueueNode();
		containerHead->next = NULL;
		containerHead->node = head;
		containerCur = containerHead;
	}
	printBTByFloor();
	return 0;
}

void addNode(Node* &p, int value){
	if(p == NULL){
		Node* temp = new Node();
		temp->value = value;
		temp->left = NULL;
		temp->right = NULL;
		p = temp;
	}else{
		if(value < p->value)
			addNode(p->left, value);
		else
			addNode(p->right, value);
	}
}

/*
 *  
 */
void printBTByFloor(){
	if(containerHead == NULL)
		return;
	cout<<containerHead->node->value<<" ";

	if(containerHead->node->left){
		QueueNode* l = new QueueNode();
		l->node = containerHead->node->left;
		l->next = NULL;
		containerCur->next = l;
		containerCur = l;
	}
	if(containerHead->node->right){
		QueueNode* r = new QueueNode();
		r->node = containerHead->node->right;
		r->next = NULL;
		containerCur->next = r;
		containerCur = r;
	}

	QueueNode* temp = containerHead;
	containerHead = containerHead->next;
	delete temp;

	printBTByFloor();
}

/*
 *  
 */
void printBT(Node* p){
	if(p == NULL)
		return;

	printBT(p->left);
	cout<<p->value<<" ";
	printBT(p->right);
}