学步园

这道题纠结了一天多了。好郁闷。

看到这题就感觉，呀，不算太难，搞定上自习去。（P.S. 这个是我昨天下午的想法）。事实证明，写到7点半，建树有点纠结。而我感觉还是应该去上上自习，就去自习了。 = =。效率不高。

我当时的问题就是，我把这样一个BST树以完全二叉树（空节点标记为-1）存到了一个数组里，需要把这个数组用指针建成一棵树。

当时建得不对。

昨晚到实验室，经CW提醒，可以用BFS 。然后就纠结在BFS上了 = =。后来想一种更简单点的，就用node结构体将tmp中的数字读取，然后通过node之间相互连接子节点，然后那个头指针就是node[1]了，这个方便多了，依旧WA。

今天中午，看了网上代码的输入，好神奇，输入改成那种了。就是输入x层的时候，遍历x-1层的节点，是否有大于1的，如果大于1，证明它有子节点。依旧WA。

那个时候代码已经很乱了 = =。空节点的标志有-1,0。。。

已经下午3点了，寝室很闷，脑袋很涨，不写了，去上自习去。

今天降温。穿的薄 = =。冷冷的，脑子感觉清醒不少。

在自习室突然想起一种做法，就是，既然已经为空了，就把指针赋为NULL多好，省的麻烦！恩。然后就复习离散了。做我最讨厌的证明题，神马合取范式，神马前束范式。。。做题，感觉不错。晚上继续~~~

刚才把代码改了改，依旧WA。快抓狂死了 = =。。。！！！

后来，看排序 = =。呀。= =。看人家排序。。。= =。我想去死！sort( a+1, a+n)  = =。。应该是sort(a+1,a+n+1) = =。。

改了后，提交。。。鲜艳的AC，泪奔啊~~~！！！

呃，我的思路是，建成树后，中序遍历（空节点不遍历），遍历的时候将已经排好序的数放到树里。然后再后序遍历即可。

上自习去~~~明天考离散~~~~~小媛要加油~~！！/(^o^)/~

#include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <string.h><br /> #include <algorithm><br /> #define MAX 260<br /> using namespace std;<br /> int n,m;<br /> typedef struct BST{<br /> int num;<br /> BST *r,*l;<br /> }BST;<br /> BST *head,node[MAX];<br /> int cou,a[MAX];<br /> int couu,counn;<br /> int output[MAX];<br /> void init()<br /> {<br /> head = NULL;<br /> memset( node,'/0',sizeof(node) );<br /> cou = couu = counn = 1 ;<br /> }<br /> void Inorder( BST *&head ) // Inorder traversal. Give the nums of sorted array to the point head.<br /> {<br /> if( head == NULL )<br /> return ;<br /> Inorder( head -> l );<br /> head->num = a[couu++]; // This.<br /> Inorder( head ->r );<br /> }<br /> void Post( BST *&head )<br /> {<br /> if( head == NULL )<br /> return ;<br /> Post( head -> l );<br /> Post( head -> r );<br /> output[counn++] = head->num; // = =.For output should has no extra space .<br /> }<br /> void Output()<br /> {<br /> printf("%d",output[1]);<br /> for(int i=2; i<counn; i++)<br /> printf(" %d",output[i]);<br /> printf("/n");<br /> }<br /> int main(void)<br /> {<br /> char c;<br /> int x,y;<br /> while( scanf("%d",&n)!=EOF )<br /> {<br /> init();<br /> for(int i=1; i<=n; i++)<br /> scanf("%d",&a[i]);<br /> sort( a+1,a+n+1 ); // I hate sort !!!!!!<br /> scanf("%d",&m);<br /> node[1].num = n;<br /> for(int k=2; k<=m; k++)<br /> {<br /> for(int i = (1<<(k-2)); i<(1<<(k-1)); i++) // the input is based on their parent node.<br /> if( node[i].num > 1 )<br /> {<br /> scanf("%d %d",&x,&y);<br /> node[2*i].num = x;<br /> node[2*i+1].num = y;<br /> }<br /> }<br /> node[0].num = n;<br /> for(int i=1; i<(1<<m)/2; i++)<br /> {<br /> if( node[i/2].num == 0 )<br /> continue;<br /> if( node[2*i].num == 0 ) // If the i 's left child is empty, the point should be NULL. So as the<br /> node[i].l = NULL; //right child.<br /> else<br /> node[i].l = &node[2*i];<br /> if( node[2*i+1].num == 0 )<br /> node[i].r = NULL;<br /> else<br /> node[i].r = &node[2*i+1];<br /> }<br /> head = &node[1];<br /> Inorder( head );<br /> Post( head );<br /> Output();<br /> }<br /> return 0;<br /> }<br />