上个星期不清楚比赛时间，原以为是周天呢，所以周六没来，错过了比赛，想找个时间把题做一做，但一直忙着复习，终于还是抽空把它做完了，其实题目不难，都是关于数据结构的，不过时间有点远了，做起来还是要费点时间的，权当复习数据结构了吧。
题意：给出一棵二叉树，只有叶子节点有重量，二叉树平衡的条件是DL*WL == DR *WR，递归的给出二叉树中的DL、WL、DR、WR，判断一下二叉树是否平衡。
解题过程：递归的输入，如果WL和WR都不为0，判断是否平衡，然后回溯判断是否平衡。开始的时候忘了判断中间的点是否平衡，所以一直WA。还有一种说法是，只判断叶子节点是否平衡就可以了，没验证，不知道对错。
题意：给出一个二叉树，二叉树的左右孩子严格分别位于父亲节点的一个单位出，即，若父亲结点坐标是x，则左孩子节点坐标为x-1，右孩子节点为x+1，给出每个节点上树叶的重量，求从最左边到最右边每堆树叶的重量，叶子节点是树叶重量不计。
解题过程：题目中给出字符的长度不超过80个，即最左点不会比根节点小多余80 ，最右点不会比根节点大多余80 ，设根节点的坐标为80 ，接下来求出每个点的树叶重量就行了。
解题过程：其实这题刚看完的时候真没想到怎么做，后来在讨论的时候听他们说才想到的，记得当时学数据结构的时候，还做过一次实验是，根据给出的二叉树的前序和中序序列可以唯一确定一棵二叉树，现在正好用到了这个结论，如果两颗二叉树的前序和中序序列相同，那么这两颗二叉树相同。
解题过程：Huffman编码，其实如果按照书上给出的方法建Huffman树真的很繁琐，而且还要算出二进制字符的长度，记得在bianchengla上做过一题，当时还傻傻的写了Huffman树，然后计算长度呢，结果怎么改都超时，后来看了别人的解题报告，知道用优先队列做，不过这题数据中只有一种字符的情况，这种情况下输出字符串的长度就可以了。
解题思路：呃，这题做的还是比较有成就感的，如果只是让输出前缀式的话，我还会用栈模拟一下，但是现在是让输出前缀、中缀、后缀式，感觉真的很繁琐，记得当时有一种算数表达树，它是一颗二叉树，但它的前序、中序、后序遍历就是表达式的前缀、中缀、后缀式，专门上网上搜了一下，自己用c语言改了一下，样例是过了，不过总也不能A，不知道什么缘故，让ZJH看了一下，原来我忽略了一种情况，a+b-c#这种情况下应该从后往前搜，所以WA了，改了之后就A了。
参考代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <math.h> #include <malloc.h> #define N 105 using namespace std; struct node { char c ; struct node *lc , *rc ; }*p , *root ; char str[N] ; void Built( int left , int right , struct node *p ) { int id , k ; if ( str[left] == '(' ) { //检查括号是否匹配 id = left + 1 ; k = 0 ; while ( id < right && k >= 0 ) { if ( str[id] == '(' ) k++ ; if ( str[id] == ')' ) k-- ; id++ ; } //如果左右边界为括号，则都往里缩一个 if ( id == right ) { left++ ; right--; } } if ( right < left ) { return ; } //需找不在括号里的'+','-' id = right ; k = 0 ; while ( ( str[id] != '+' && str[id] != '-' && id > left) || k != 0 ) { if ( str[id] == '(' ) k++ ; if ( str[id] == ')' ) k-- ; id-- ; } //找到了 if ( id > left ) { p->c = str[id] ; p->lc = ( struct node *) malloc( sizeof ( struct node)) ; p->rc = ( struct node *) malloc( sizeof ( struct node)) ; Built( left , id - 1 , p->lc ) ; Built( id + 1 , right , p->rc ) ; } else { //如果没找到'+','-'，则找'*','/' id = right ; k = 0 ; while ( ( str[id] != '*' && str[id] != '/' && id > left ) || k != 0 ) { if ( str[id] == '(' ) k++ ; if ( str[id] == ')' ) k-- ; id-- ; } //找到了'*','/' if ( id > left ) { p->c = str[id] ; p->lc = ( struct node *) malloc( sizeof ( struct node )) ; p->rc = ( struct node *) malloc( sizeof ( struct node )) ; Built( left , id - 1 , p->lc ) ; Built( id + 1 ,right , p->rc ) ; } //没有找到 else { p->c = str[left] ; p->lc = p->rc = NULL ; } } return ; } void output1( struct node *p ) { printf ( "%c" , p->c ) ; if ( p->lc != NULL ) output1( p->lc ) ; if( p->rc != NULL ) output1( p->rc ) ; } void output2( struct node *p ) { if ( p->lc != NULL ) output2( p->lc ) ; printf ( "%c" , p->c ) ; if( p->rc != NULL ) output2( p->rc ) ; } void output3( struct node *p ) { if ( p->lc != NULL ) output3( p->lc ) ; if( p->rc != NULL ) output3( p->rc ) ; printf ( "%c" , p->c ) ; } int main() { int len , id , k ; //freopen( "input.txt" , "r" , stdin ) ; while( scanf ( "%s" , str ) != EOF ) { len = strlen( str ); while ( str[len] != '#') len-- ; id = 0 ; k = 0 ; //检查括号是否匹配 while ( id < len && k >= 0 ) { if ( str[id] == '(' ) k++ ; if ( str[id] == ')' ) k-- ; id++ ; } if( k == 0 ) { root = ( struct node *) malloc( sizeof( struct node )) ; root->lc = root->rc = NULL ; //建树 Built( 0 , len - 1 , root ) ; //前序遍历 output1( root ) ; printf( "\n" ) ; //中序遍历 output2( root ) ; printf ( "\n" ) ; //后序遍历 output3( root ) ; printf ( "\n" ) ; } } return 0 ; }