需求:数串由2^n个'0' '1'数串组成,对于一个数串,有01混合出现,则视为F,全0数串为B,全1数串为I。
将给定数串进行切割,如10010011可以用二叉树表示为
F(10010011)
/ \
F (1001) F(0011)
/ \ / \
F(10) F(01) B(00) I(11)
/ \ / \ / \ / \
I(1)B(0) B(0) I(1) B(0)B(0) I(1)I(1)
思路:由上述可以看出,FBI树是一棵满二叉树,可以使用逆向建树方法,以逐层建树的方法,先建立叶子节点层,然后生成其上层节点,如此类推,可以快速得到二叉树。
而且我们可以看到孩子的值与双亲的值的关系如下:
左/右孩子值 左/右孩子值 双亲值
F + F = F
F + B = F
F + I = F
I + B = F
B + B = B
I + I = I
由此确定双亲的值。
代码实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h> struct tree_node;
struct tree_node{
struct tree_node *lc;
struct tree_node *rc;
char key;
};
typedef struct tree_node treenode; void create_fbitree(treenode **T, char *num){
int numlen, k;
int levelcnt;
treenode *nodetemp, *levelnode, *levelnodekids; numlen = strlen(num);
levelcnt = numlen;
levelnode = (treenode*)malloc(sizeof(treenode)*levelcnt);
for(k=0; k<levelcnt; k++){
(levelnode+k)->lc = NULL;
(levelnode+k)->rc = NULL;
if(num[k]=='1')
(levelnode+k)->key = 'I';
else
(levelnode+k)->key = 'B';
}
levelcnt = levelcnt/2;
levelnodekids = levelnode; while(levelcnt){
levelnode = (treenode*)malloc(sizeof(treenode)*levelcnt);
for(k=0; k<levelcnt; k++){
(levelnode+k)->lc = levelnodekids+k*2;
(levelnode+k)->rc = levelnodekids+k*2+1;
if((levelnodekids+k*2)->key=='B'&&(levelnodekids+k*2+1)->key=='B')
(levelnode+k)->key = 'B';
else if((levelnodekids+k*2)->key=='I'&&(levelnodekids+k*2+1)->key=='I')
(levelnode+k)->key = 'I';
else
(levelnode+k)->key = 'F';
}
levelcnt = levelcnt/2;
levelnodekids = levelnode;
}
*T = levelnode;
} void pre_visit_tree(treenode *T){
if(T!=NULL){
printf("%c ", T->key);
pre_visit_tree(T->lc);
pre_visit_tree(T->rc);
}
else{
return;
}
} int main(void){
treenode *T;
char num[1000]; if(gets(num)==NULL)
return 0;
create_fbitree(&T, num);
pre_visit_tree(T); system("pause");
return 0;
}