【RQNOJ】PID21 / FBI树

题目描述

　　我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

　　FBI树是一种二叉树1，它的结点类型也包括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树，并输出它的后序遍历2序列。

分析：没难度，用递归即可解决

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct FBI_NODE {
    char type;
    struct FBI_NODE *pleft;
    struct FBI_NODE *pright;
};

static char nodeType(char* str, int start, int end)
{
    char type = str[start] == "0" ? 'B' : 'I';
    int i=start + 1;

    while (i <= end)
    {
        if (str[i] == str[start])
        {
            i++;
        }
        else
            return 'F';
    }
    return type;
}

static  struct FBI_NODE* parseSeries(char* str, int start, int end)
{
    struct FBI_NODE* root= NULL;
    char type = nodeType(str,start,end);

    root = (struct FBI_NODE*)calloc(sizeof(struct FBI_NODE), 1);
    if (NULL == root)
    {
        printf("malloc error\n");
        return NULL;
    }

    root->type = type;
    if (start < end)
    {
        root->pleft = parseSeries(str,start, (start + end)/2);
        root->pright = parseSeries(str,(start+end)/2 + 1, end);
    }
    return root;
}

static void visitFBI_rootLast(struct FBI_NODE *root)
{
    if (!root)
    {
        return;
    }

    if (root->pleft)
    {
        visitFBI_rootLast(root->pleft);
    }
    if (root->pright)
    {
        visitFBI_rootLast(root->pright);
    }
    printf("%c", root->type);
}
static void destroiyFBItree(struct FBI_NODE *root)
{
    printf("free nodes[ NOT IMPLEMENTED]\n");
}

int main(int argc, char** argv)
{
    char* str = "10001011";
    struct FBI_NODE *root = parseSeries(str, 0, 7);
    visitFBI_rootLast(root);
    destroiyFBItree(root);
}