创建FBI树

时间:2023-03-08 17:08:23
创建FBI树

需求:数串由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;
}