/*
2．给定以下二叉树:

struct node_t

{

node_t *left, *right;

int value;

};
要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);

输出以 node 为根的二叉树第 m 层的第 k 个节点值.

(level, k 均从 0 开始计数)

注意：

.此树不是完全二叉树；

.所谓的第K个节点，是本层中从左到右的第K个节点 

第三题 系统设计题
*/
#include <iostream>
using namespace std;

const int MAX_LENGTH = 100;

struct node_t
{
	node_t *left;
	node_t *right;
	int value;
};

node_t *queue[100];
int level = 0; // 记录第几层
int count = 0; // 记录第level层的第几个结点
int top = -1;
int rear = -1;

bool IsQueueEmpty()
{
	return top == rear;
}

void EnQueue(node_t *node)
{
	queue[++rear] = node;
}

node_t* DeQueue()
{
    return queue[++top];
}

void CreateBiTree(node_t **root)
{
	char ch;

	cin >> ch;
	
	if (ch == '*')
	{
		*root = NULL;
		return;
	}
	else
	{
		*root = new node_t;
		(*root)->value = ch;
		CreateBiTree(&(*root)->left);
		CreateBiTree(&(*root)->right);
	}
}

node_t* foo(node_t *node, unsigned int m, unsigned int k)
{
	node_t *p = node;
    int last = -1;
    
	if (p != NULL)
	{
		EnQueue(p); // 入队
		while (!IsQueueEmpty())
		{
			last = rear;
			while (top < last)
			{
				node_t *q = DeQueue();
				count++; // 当前层的第X个结点

				if (level == m && count == k)
				{
					cout << q->value << endl;
					return q;
				}

				if (q->left != NULL)
				{
					EnQueue(q->left);
				}

				if (q->right != NULL)
				{
					EnQueue(q->right);
				}
			}

			level++;
            count = 0;
		}
	}

	cout << "找不到符合的结点" << endl;

	return NULL;
}

int main()
{
	node_t *root;
	CreateBiTree(&root);
	cout << "树建立完毕" << endl;

	foo(root, 1, 1);

	return 0;
}