#include <iostream>
#include <queue>
#include <stack>
 
namespace
{
 
}
 
struct Node
{
	float value;//木のノードの持つ値
	int num;//ノード番号
	Node* left;//左の子
	Node* right;//右の子
};
 
//numは自動で増える
Node* makeNode(float value)
{
	static int n = 0;
	Node* p = new Node{ value, n, nullptr, nullptr };
	n++;
	return p;
}
 
void PrintNode(Node* node)
{
	//自分のノード番号、左の子のノード番号、右の子のノード番号を表示
	int myNum = node->num;
	int leftNum = -1, rightNum = -1;
	if (node->left != nullptr)
		leftNum = node->left->num;
	if (node->right != nullptr)
		rightNum = node->right->num;
 
	std::cout << myNum << ", " << leftNum << ", " << rightNum << std::endl;
	//とりあえずvalueはスルー
}
 
void BFS(Node* root)
{
	std::queue<Node*>  myQueue;
	myQueue.push(root);
 
	while (!myQueue.empty())
	{
		Node* p = myQueue.front();
		myQueue.pop();
		std::cout << p->num << " ";
		if (p->left != nullptr)
			myQueue.push(p->left);
		if (p->right != nullptr)
			myQueue.push(p->right);
	}
}
 
void DFS(Node* root)
{
	std::stack<Node*>  myStack;
	myStack.push(root);
 
	while (!myStack.empty())
	{
		Node* p = myStack.top();
		myStack.pop();
		std::cout << p->num << " ";
		if (p->right != nullptr)
			myStack.push(p->right);
		if (p->left != nullptr)
			myStack.push(p->left);
 
	}
}
 
int main()
{
	Node* p[11]; //ノードのアドレスの配列
	Node* pRoot = nullptr;
	p[0] = makeNode(0.0);
	p[1] = makeNode(0.1);
	p[2] = makeNode(0.2);
	p[3] = makeNode(0.3);
	p[4] = makeNode(0.4);
	p[5] = makeNode(0.5);
	p[6] = makeNode(0.6);
	p[7] = makeNode(0.7);
	p[8] = makeNode(0.8);
	p[9] = makeNode(0.9);
	p[10] = makeNode(1.0);
 
	p[0]->left = p[1]; p[0]->right = p[2];
	p[1]->left = p[3]; p[1]->right = p[4];
	p[2]->left = p[5]; p[2]->right = p[6];
	p[3]->left = p[7]; p[3]->right = p[8];
	p[5]->left = p[9];
	p[6]->right = p[10];
 
	pRoot = p[0];
	BFS(pRoot);
	//r->rll
	//for (int i = 0; i < 9; i++)
	//{
	//	PrintNode(p[i]);
	//}
	//std::cout << pRoot->left->right->num 
	std::cout<< std::endl;
	DFS(pRoot);
 
	return 0;
}