Chinaunix首页 | 论坛 | 博客
  • 博客访问: 671459
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2017-07-16 14:10:36

题目描述

  我们可以把由“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序列。



分析:没难度,用递归即可解决

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. struct FBI_NODE {
  5.     char type;
  6.     struct FBI_NODE *pleft;
  7.     struct FBI_NODE *pright;
  8. };

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

  13.     while (i <= end)
  14.     {
  15.         if (str[i] == str[start])
  16.         {
  17.             i++;
  18.         }
  19.         else
  20.             return 'F';
  21.     }
  22.     return type;
  23. }

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

  28.     root = (struct FBI_NODE*)calloc(sizeof(struct FBI_NODE), 1);
  29.     if (NULL == root)
  30.     {
  31.         printf("malloc error\n");
  32.         return NULL;
  33.     }

  34.     root->type = type;
  35.     if (start < end)
  36.     {
  37.         root->pleft = parseSeries(str,start, (start + end)/2);
  38.         root->pright = parseSeries(str,(start+end)/2 + 1, end);
  39.     }
  40.     return root;
  41. }

  42. static void visitFBI_rootLast(struct FBI_NODE *root)
  43. {
  44.     if (!root)
  45.     {
  46.         return;
  47.     }

  48.     if (root->pleft)
  49.     {
  50.         visitFBI_rootLast(root->pleft);
  51.     }
  52.     if (root->pright)
  53.     {
  54.         visitFBI_rootLast(root->pright);
  55.     }
  56.     printf("%c", root->type);
  57. }
  58. static void destroiyFBItree(struct FBI_NODE *root)
  59. {
  60.     printf("free nodes[ NOT IMPLEMENTED]\n");
  61. }

  62. int main(int argc, char** argv)
  63. {
  64.     char* str = "10001011";
  65.     struct FBI_NODE *root = parseSeries(str, 0, 7);
  66.     visitFBI_rootLast(root);
  67.     destroiyFBItree(root);
  68. }


阅读(1707) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~