#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;

//	TreeNode(int x) : val(x), left(NULL), right(NULL){}
};
void TreeTraversePre(TreeNode* root,vector<int> &vec_Result);


class TreePrinter {
public:
	vector<vector<int> > printTree(TreeNode* root) {

		vector<vector<int> > vec_Print;
		queue<TreeNode*> que_Temp;
		if(NULL == root)
			return vec_Print;

		TreeNode *last;
		TreeNode *nlast;

		last = root;
		nlast = NULL;
		que_Temp.push(last);

		vector<int> vec_Temp;

		while(que_Temp.size() != 0)
		{

			if(NULL != que_Temp.front()->left)
			{
				que_Temp.push(que_Temp.front()->left) ;
				nlast = (que_Temp.front()->left);
			}

			if(NULL != que_Temp.front()->right)
			{
				que_Temp.push(que_Temp.front()->right);
				nlast = (que_Temp.front()->right);
			}

			vec_Temp.push_back(que_Temp.front()->val);

			if(que_Temp.front() == last)
			{
				last = nlast;
				vec_Print.push_back(vec_Temp);
				vec_Temp.clear();
			}

			que_Temp.pop();

		}

		return vec_Print;
	}
};


//前后中  序，就是遍历到跟的时间为  开始 最后 中间
//1. 前序遍历，访问的顺序为根->左->右；
void TreeTraversePre(TreeNode* root,vector<int> &vec_Result)
{
	if(NULL == root) return;

	vec_Result.push_back(root->val);


	if(NULL != root->left)
	{
//		vec_Result.push_back(root->left->val);
		TreeTraversePre(root->left, vec_Result);
	}

	if(NULL != root->right)
	{
//		vec_Result.push_back(root->right->val);
		TreeTraversePre(root->right, vec_Result);
	}
	return;
}

//2. 中序遍历，访问的顺序为左->根->右；
void TreeTraverseMid(TreeNode* root,vector<int> &vec_Result)
{
	if(NULL == root) return;



	if(NULL != root->left)
	{
//		vec_Result.push_back(root->left->val);
		TreeTraverseMid(root->left, vec_Result);
	}

	vec_Result.push_back(root->val);


	if(NULL != root->right)
	{
//		vec_Result.push_back(root->right->val);
		TreeTraverseMid(root->right, vec_Result);
	}


	return;
}


//3. 后序遍历，访问的顺序为左->右->根；
void TreeTraverseBeh(TreeNode* root,vector<int> &vec_Result)
{
	if(NULL == root) return;



	if(NULL != root->left)
	{
//		vec_Result.push_back(root->left->val);
		TreeTraverseBeh(root->left, vec_Result);
	}



	if(NULL != root->right)
	{
//		vec_Result.push_back(root->right->val);
		TreeTraverseBeh(root->right, vec_Result);
	}

	vec_Result.push_back(root->val);

	return;
}


struct TreeNode** CreateTree()
{
	struct TreeNode* stTreeNode[9];
//	stTreeNode = (struct TreeNode** ) malloc(sizeof(struct TreeNode*));
//	memset(stTreeNode, 0, sizeof(struct TreeNode*));

	for(int i = 0; i<9; i++)
	{
		stTreeNode[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
		memset(stTreeNode[i], 0, sizeof(struct TreeNode));

		stTreeNode[i]->val = i+65;
		printf("i:%d\n",stTreeNode[i]->val);

	}
	stTreeNode[8]->val = 'K';
	printf("00000\n");

	for(int i = 0; i<9; i++)
	{
		printf("i:%d\n",stTreeNode[i]->val);
	}


	stTreeNode[0]->left = stTreeNode[1];

	stTreeNode[1]->right = stTreeNode[2];


	stTreeNode[2]->left = stTreeNode[3];

	stTreeNode[0]->right = stTreeNode[4];
	stTreeNode[4]->right = stTreeNode[5];
	stTreeNode[5]->left = stTreeNode[6];
	stTreeNode[6]->left = stTreeNode[7];
	stTreeNode[6]->right = stTreeNode[8];


	return stTreeNode;
}


int main(int argc, char* argv[])
{
//	struct TreeNode** stTreeNode;
//	stTreeNode = CreateTree();
	struct TreeNode* stTreeNode[9];
//	stTreeNode = (struct TreeNode** ) malloc(sizeof(struct TreeNode*));
//	memset(stTreeNode, 0, sizeof(struct TreeNode*));

	for(int i = 0; i<9; i++)
	{
		stTreeNode[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
		memset(stTreeNode[i], 0, sizeof(struct TreeNode));

		stTreeNode[i]->val = i+65;
		printf("i:%d\n",stTreeNode[i]->val);

	}
	stTreeNode[8]->val = 'K';
	printf("00000\n");

	for(int i = 0; i<9; i++)
	{
		printf("i:%c\n",stTreeNode[i]->val);
	}


	stTreeNode[0]->left = stTreeNode[1];

	stTreeNode[1]->right = stTreeNode[2];


	stTreeNode[2]->left = stTreeNode[3];

	stTreeNode[0]->right = stTreeNode[4];
	stTreeNode[4]->right = stTreeNode[5];
	stTreeNode[5]->left = stTreeNode[6];
	stTreeNode[6]->left = stTreeNode[7];
	stTreeNode[6]->right = stTreeNode[8];



	printf("root:%c\n",stTreeNode[0]->val);
	struct TreeNode* root;
	root = stTreeNode[0];
//	for(int i = 0; i<9; i++)
	{
//		printf("len:%d\n",strlen((char*)(stTreeNode[i]->val)));
//		printf("Val:%c\n",stTreeNode[i]->val);

//		printf("i:%lu\n",sizeof(stTreeNode[i]));
	}

	vector<int> vec_Result;


	TreeTraversePre(root,vec_Result);

	printf("TreeTraversePre\n");
	vector<int>::iterator it;
	for(it = vec_Result.begin(); it != vec_Result.end();it++)
	{
		printf("Val:%c\n",*it);
	}
	vec_Result.clear();

	TreeTraverseMid(root,vec_Result);

	printf("TreeTraverseMid\n");
//	vector<int>::iterator it;
	for(it = vec_Result.begin(); it != vec_Result.end();it++)
	{
		printf("Val:%c\n",*it);
	}

	vec_Result.clear();

	TreeTraverseBeh(root,vec_Result);

	printf("TreeTraverseBeh\n");
//	vector<int>::iterator it;
	for(it = vec_Result.begin(); it != vec_Result.end();it++)
	{
		printf("Val:%c\n",*it);
	}
}