回 帖 发 新 帖 刷新版面

主题:请高手进来看一下

如果用大小写字母标识二叉树结点,则一棵二叉树可以用符合下面语法图的字符序列表示,试写一个递归算法,有这种形式的字符序列,建立相应的二叉树的二叉链表存储结构。
  
 输入形式为A(B(#,D),C(E(#,F),#))

不知各位有没有做过这样的题目
研究一下啊

回复列表 (共6个回复)

沙发

B="N(L,R)"
关键是划分L和R,就是找到中间的',',扫描的时候,对左右括号进行统计,一开始c=0,遇到一个'(',c++,遇到一个')',c--,当扫描到一个','且这个时候c==1,那就找到了。然后就可以简单的递归建树了。

板凳

版主这个算法,我也知道,问题是我不知道如何写成代码,而且要用递归,真的很难写出来.不知版主能否帮忙写一下
多谢谢了

3 楼

#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 楼

程序没有对输入语法进行检查,输入的字符须是'(',')',','和一般字符,PrintBTree()也是用递归打印的,实际上就是先根遍历,最后结果是,输出和输入一致.

5 楼

多谢版主,你真是太厉害了
以后得多多向你学习

6 楼

void BuildBiTree(BiTree &bt, char *s, int &i)
/* 单遍扫描广义表形式的字符序列s,   */
/* 建立相应的二叉树bt。              */
/* i为扫描s时当前字符的序号,初值为0 */

如果用这个函数头来做的话,不知又该如何做
好像难度增加了很多

我来回复

您尚未登录,请登录后再回复。点此登录或注册