FBI树   （建立）遍历二叉树

题目：我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
　　FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2 ^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
　　1)T的根结点为R，其类型与串S的类型相同；
　　2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
　　现在给定一个长度为2 ^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。 输入格式 　　第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2^N的“01”串。 输出格式 　　包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。 样例输入 3
10001011 样例输出 IBFBBBFIBFIIIFF

方法一）建立二叉树，然后遍历

#include<iostream> 
#include<cstdlib> 
using namespace std; 
int length;
char s[1<<10];
typedef struct Node{
char node;
struct Node *left;
struct Node *right;
}tNode;

char FBI(int begin,int end)
{
bool zero = false;
bool one = false;
for(int i = begin;i <= end;i ++)
{
if(s[i] == '0')
{
zero = true;
}
if(s[i] == '1')
{
one = true;
}
if(zero && one)
break;
}
if(zero && !one)
{
return 'B';
}
if(one && !zero)
{
return 'I';
}
if(zero && one)
{
return 'F';
}

}

tNode* build(int begin,int end)
{

    tNode*tree = (tNode*)malloc(sizeof(tNode));
tree->node = FBI(begin,end);
tree->left = tree->right = NULL;
if(begin != end)
{
tree->left = build(begin,(begin+end)/2);
    tree->right = build((begin+end)/2 + 1,end);
}

return tree;
}

void preVist(tNode *tree)
{
if(tree)
{
preVist(tree->left);
    preVist(tree->right);
    cout << tree->node;
}

}

int main()
{
int n;
length = 1;
cin >> n;
cin >> s;
while(n --)
{
length *= 2;
}
length --;
tNode *Tree ;
Tree = build(0,length);
preVist(Tree);
cout << endl;
free(Tree);
return 0;
}

之前在建立二叉树的时候，结束递归的条件是这样写的：

tNode* build(int begin,int end)
{

    tNode*tree = (tNode*)malloc(sizeof(tNode));
tree->node = FBI(begin,end);
tree->left = tree->right = NULL;
if(begin == end)
tree = NULL;
else
{
tree->left = build(begin,(begin+end)/2);
    tree->right = build((begin+end)/2 + 1,end);
}

return tree;
}

傻傻地清空了叶子结点，遍历出来的结果就不正确了。

方法二）不需要建立二叉树，在遍历过程中因为先判断左右子树并输出，最后根据左右子树来判断结点并输出，所以是后序遍历。 http://www.cnblogs.com/yylogo/archive/2011/08/07/RQNOJ-21.html

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char str[1025];
char put[3] = {'B', 'I' ,'F'};

int srch(int start, int end)
{
int i, j;
if(start == end){
    printf("%c", put[str[start] - '0']);
return str[start] - '0';
}
i = srch(start, (start + end) / 2);//左子树 
j = srch((start + end) / 2 + 1, end);//右子树 
if(i == j){ //如果左右子树相同 
printf("%c", put[i]);
return i;
}else{//左右子树不相同 
printf("%c", 'F');
return 2;
}
}

int main()
{
int n;
scanf("%d\n", &n);
scanf("%s", str);
srch(0, strlen(str) - 1);
printf("\n");
return 0;
}