NYOJ-63 小猴子下落（二叉树及优化算法详解）

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
struct node
{
int data;
int flag;
node *lchild,*rchild;
node();
};
node::node()
{
flag=-;
rchild=lchild=NULL;
}
void createTree(int d,node *&root)
{
queue<node *> q;
while(!q.empty())
q.pop();
root=new node;
static int count=;
root->data=++count;
q.push(root);
node *t=root;
while(count!=pow(,d)-)
{
t=q.front();
q.pop();
t->lchild=new node;
t->lchild->data=++count;
q.push(t->lchild);
t->rchild=new node;
t->rchild->data=++count;
q.push(t->rchild);
}
t=NULL;
count=;
}
/*
void LevelOrder(node *root)
{ //队列实现
queue<node *> q;
node *t=root;
if(t!=NULL) q.push(t); //根非空，入队
while(!q.empty()) //队不空
{
t=q.front();
q.pop(); //出队
cout<<t->data<<" ";
if(t->lchild)
q.push(t->lchild); //遍历左孩子
if(t->rchild)
q.push(t->rchild); //遍历右孩子
} }
*/
void Go(int &t,node *&root)
{
if(root->lchild&&root->rchild){
if(root->flag==-)
{
Go(t,root->lchild);
root->flag=;
}
else
{
Go(t,root->rchild);
root->flag=-;
}
}
else
t=root->data;
} int main()
{
int d,num;
while(cin>>d>>num,d&&num){
node *root=NULL;
createTree(d,root);
int t;
for(int i=;i<num;i++)
Go(t,root);
cout<<t<<endl;
}
return ;
}