主题:请高手进来看一下
海上飞洪
[专家分:520] 发布于 2006-04-23 15:15:00
如果用大小写字母标识二叉树结点,则一棵二叉树可以用符合下面语法图的字符序列表示,试写一个递归算法,有这种形式的字符序列,建立相应的二叉树的二叉链表存储结构。
输入形式为A(B(#,D),C(E(#,F),#))
不知各位有没有做过这样的题目
研究一下啊
回复列表 (共6个回复)
沙发
rickone [专家分:15390] 发布于 2006-04-23 18:39:00
B="N(L,R)"
关键是划分L和R,就是找到中间的',',扫描的时候,对左右括号进行统计,一开始c=0,遇到一个'(',c++,遇到一个')',c--,当扫描到一个','且这个时候c==1,那就找到了。然后就可以简单的递归建树了。
板凳
海上飞洪 [专家分:520] 发布于 2006-04-23 23:01:00
版主这个算法,我也知道,问题是我不知道如何写成代码,而且要用递归,真的很难写出来.不知版主能否帮忙写一下
多谢谢了
3 楼
rickone [专家分:15390] 发布于 2006-04-24 16:15:00
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct _bnode{
char data;
struct _bnode *lchild,*rchild;
}BNode,*BTree;
void CreateBTreeStr(BTree *root,char *str,int n)
{
int i,c;
BTree p;
if(n==1)
{
if(*str=='#')
*root=NULL;
else
{
p=(BTree)malloc(sizeof(BNode));
*root=p;
p->data=*str;
p->lchild=p->rchild=NULL;
}
}
else
{
c=0;
for(i=0;i<n;++i)
{
if(str[i]=='(')
c++;
else if(str[i]==')')
c--;
else if(str[i]==',')
{
if(c==1)/*找到了*/
break;
}
}
p=(BTree)malloc(sizeof(BNode));
*root=p;
p->data=*str;
CreateBTreeStr(&p->lchild,str+2,i-2);
CreateBTreeStr(&p->rchild,str+i+1,n-i-2);
}
}
void PrintBTree(BTree root)
{
if(root==NULL)
{
printf("#");
return;
}
printf("%c",root->data);
if(root->lchild!=NULL||root->rchild!=NULL)
{
printf("(");
PrintBTree(root->lchild);
printf(",");
PrintBTree(root->rchild);
printf(")");
}
}
void main()
{
BTree bt;
char sz_input[256];
scanf("%s",sz_input);
CreateBTreeStr(&bt,sz_input,strlen(sz_input));
PrintBTree(bt);
printf("\n");
}
4 楼
rickone [专家分:15390] 发布于 2006-04-24 16:19:00
程序没有对输入语法进行检查,输入的字符须是'(',')',','和一般字符,PrintBTree()也是用递归打印的,实际上就是先根遍历,最后结果是,输出和输入一致.
5 楼
海上飞洪 [专家分:520] 发布于 2006-04-25 12:29:00
多谢版主,你真是太厉害了
以后得多多向你学习
6 楼
海上飞洪 [专家分:520] 发布于 2006-04-26 10:55:00
void BuildBiTree(BiTree &bt, char *s, int &i)
/* 单遍扫描广义表形式的字符序列s, */
/* 建立相应的二叉树bt。 */
/* i为扫描s时当前字符的序号,初值为0 */
如果用这个函数头来做的话,不知又该如何做
好像难度增加了很多
我来回复