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

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心

苦海澜石

凯发app官方网站首页　| 　博文目录　| 　关于我

khls27

  • 博客访问： 752898
  • 博文数量： 144
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1150
  • 用 户 组： 普通用户
  • 注册时间： 2014-03-17 14:32
个人简介

小公司研发总监，既当司令也当兵！

文章分类

全部博文（144）

推荐博文
相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
【rqnoj】pid21 / fbi树

分类： 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>

  5. struct fbi_node {
  6.     char type;
  7.     struct fbi_node *pleft;
  8.     struct fbi_node *pright;
  9. };

  11. static char nodetype(char* str, int start, int end)
  12. {
  13.     char type = str[start] == "0" ? 'b' : 'i';
  14.     int i=start 1;

  16.     while (i <= end)
  17.     {
  18.         if (str[i] == str[start])
  19.         {
  20.             i;
  21.         }
  22.         else
  23.             return 'f';
  24.     }
  25.     return type;
  26. }

  28. static struct fbi_node* parseseries(char* str, int start, int end)
  29. {
  30.     struct fbi_node* root= null;
  31.     char type = nodetype(str,start,end);

  33.     root = (struct fbi_node*)calloc(sizeof(struct fbi_node), 1);
  34.     if (null == root)
  35.     {
  36.         printf("malloc error\n");
  37.         return null;
  38.     }

  40.     root->type = type;
  41.     if (start < end)
  42.     {
  43.         root->pleft = parseseries(str,start, (start end)/2);
  44.         root->pright = parseseries(str,(startend)/2 1, end);
  45.     }
  46.     return root;
  47. }

  49. static void visitfbi_rootlast(struct fbi_node *root)
  50. {
  51.     if (!root)
  52.     {
  53.         return;
  54.     }

  56.     if (root->pleft)
  57.     {
  58.         visitfbi_rootlast(root->pleft);
  59.     }
  60.     if (root->pright)
  61.     {
  62.         visitfbi_rootlast(root->pright);
  63.     }
  64.     printf("%c", root->type);
  65. }
  66. static void destroiyfbitree(struct fbi_node *root)
  67. {
  68.     printf("free nodes[ not implemented]\n");
  69. }

  71. int main(int argc, char** argv)
  72. {
  73.     char* str = "10001011";
  74.     struct fbi_node *root = parseseries(str, 0, 7);
  75.     visitfbi_rootlast(root);
  76.     destroiyfbitree(root);
  77. }


阅读(1982) | 评论(0) | 转发(0) |
0

上一篇：【rqnoj】pid54 / 麦森数

下一篇：【rqnoj】pid21 / fbi树

给主人留下些什么吧！~~
| | | | |

凯发app官方网站 copyright 2001-2010 chinaunix.net all rights reserved 北京皓辰网域网络信息技术有限公司. 凯发k8官网下载客户端中心的版权所有

感谢所有关心和支持过chinaunix的朋友们
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图