小猴子下落（二叉树）

小猴子下落

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

有一颗二叉树，最大深度为D,且所有叶子的深度都相同。所有结点从左到右从上到下的编号为1,2,3，·····，2的D次方减1。在结点1处放一个小猴子，它会往下跑。每个内结点上都有一个开关，初始全部关闭，当每次有小猴子跑到一个开关上时，它的状态都会改变，当到达一个内结点时，如果开关关闭，小猴子往左走，否则往右走，直到走到叶子结点。

一些小猴子从结点1处开始往下跑，最后一个小猴儿会跑到哪里呢？

输入

输入二叉树叶子的深度D,和小猴子数目I，假设I不超过整棵树的叶子个数，D<=20.最终以 0 0 结尾

输出

输出第I个小猴子所在的叶子编号。

样例输入

4 2
3 4
0 0

样例输出

12
7
按层遍历是对data从1到n赋值

  1 #include <iostream>
  2 using namespace std;
  3 typedef struct node
  4 {
  5     bool value;
  6     int data;
  7     node *lchild,*rchild;
  8 }binode,*bitree;
  9 int s=1;
 10 bitree a[10000000];
 11 bitree createTree(bitree root,int depth)
 12 {
 13     if(depth==1)
 14     {
 15         root=new binode;
 16         root->lchild=root->rchild=NULL;
 17         root->value=0;
 18         root->data=s;
 19         s++;
 20         return root;
 21     }
 22     else
 23     {
 24         root=new binode;
 25         root->value=0;
 26         root->data=s;
 27         s++;
 28         root->lchild=createTree(root->lchild,depth-1);
 29         root->rchild=createTree(root->rchild,depth-1);
 30     }
 31     return root;
 32 }
 33 void Traverse(bitree root)
 34 {
 35     if(root)
 36     {
 37         cout<<root->data<<" ";
 38         Traverse(root->lchild);
 39         Traverse(root->rchild);
 40     }
 41 }
 42 int monkey(bitree root)
 43 {
 44     if(root)
 45     {    
 46         if(root->lchild==NULL&&root->rchild==NULL)
 47         {
 48             if(root->value==1)
 49                 root->value=0;
 50             else
 51                 root->value=1;
 52             return root->data;
 53         }
 54         if(root->value==1)
 55         {
 56             root->value=0;
 57             return monkey(root->rchild);
 58         }
 59         else
 60         {
 61             root->value=1;
 62             return monkey(root->lchild);
 63         }
 64     }
 65 }
 66 void TraverseQueue(bitree root)
 67 {
 68     
 69     int i=1;
 70     int font=0,rear=0;
 71     if(root)
 72     {
 73         a[rear]=root;
 74         rear++;
 75     }
 76     while(rear!=font)
 77     {
 78         bitree p=a[font];
 79         font++;
 80         p->data=i;i++;
 81         if(p->lchild)
 82         {
 83             a[rear]=p->lchild;
 84             rear++;
 85         }
 86         if(p->rchild)
 87         {
 88             a[rear]=p->rchild;
 89             rear++;
 90         }
 91     }
 92 }
 93 int main()
 94 {
 95     int d,n,i;
 96     while(cin>>d>>n)
 97     {
 98         s=1;
 99         if(d==0&&n==0)
100             return 0;
101         bitree root=NULL;
102         root=createTree(root,d);
103         //Traverse(root);
104         //cout<<endl;
105         TraverseQueue(root);
106         for(i=0;i<n-1;i++)
107             monkey(root);
108         cout<<monkey(root)<<endl;
109     }
110 }