注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Aspirer's blog

停止维护,新博客地址:http://aspirer.wang/

 
 
 

日志

 
 

M叉树字符串变换  

2009-09-29 23:03:23|  分类: 学习心得 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

M叉树字符串变换 - aspirer - Aspirers blog

 

设 M 叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分

 (设为一个字符) 和用“( )”,括起来的各子树的列表 (如有子树的话) ,各子列表间用“

,”,分隔。例如下面的三叉树可用列表 a( b( c,d ),e,f( g,h,i ))表示。

 

本程序输入列表,生成一棵 M 叉树,并由 M 叉树输出列表。假定输入无错误。

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


#define M 3

using namespace std;

typedef struct node{
 char val;
 struct node *subTree[M];
} NODE;

char buf[255], *str = buf;
NODE *d = NULL;

NODE *makeTree( ) /*由列表生成M叉树*/
{
 int k;
 NODE *s;
 s = (NODE *)malloc(sizeof(NODE));
 s -> val = *str++ ;
 for ( k = 0 ; k < M; k++ )
 {
  s->subTree[k] = NULL;
 }
 if ( *str == '(' )
 {
  k = 0;
  do
  {
   str++;
   s->subTree[k] = makeTree() ;
   if ( *str == ')' )
   {
    str++;
    break;
   }
   k = k+1;
  } while (k < M);
 }
 return s;
}

void walkTree(NODE *t) /*由 M 叉树输出列表*/
{
 if (t != NULL)
 {
  putchar(t->val);
  if ( t -> subTree[0] == NULL )
   return ;
  putchar ( '(' ) ;
  for (int i = 0 ; i < M ; i++)
  {
   walkTree(t->subTree[i]);
   if ( i != M-1 && t->subTree[i+1] != NULL )
    putchar ( ',' ) ;
  }
  putchar ( ')' );
 }
}

int main()
{
 printf( "Enter exp:" ) ;
 scanf( "%s" , str ) ;
 d = makeTree() ;
 walkTree(d) ;
 putchar( '\n');
 return 0;
}

  评论这张
 
阅读(948)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018