【rqnoj】pid21 / fbi树-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 752898
  • 博文数量: 144
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1150
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

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

文章分类

全部博文(144)

相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·

分类: 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,(startend)/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. }


阅读(1982) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图