Martine 发表于 2018-6-25 17:52:58

二叉树转化为森林 父子关系的递归遍历

本帖最后由 Martine 于 2018-6-25 18:08 编辑

题:将如图所示的深林转化为二叉树(易)

将父子关系表示为 父(子,子......)
则该森林的数据结构可以表示为 A(B(EF)C(G)D)

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

typedef char ElemType;

typedef struct node
{
        ElemType data;
        struct node *lchild, *rchild;
}node, *btree;

void CreateBtree(btree *root)
{       
        ElemType c;
        scanf("%c", &c);
        if('#' == c){
                *root = NULL;
        }else{
                *root = (btree)malloc(sizeof(node));
                (*root)->data = c;

                CreateBtree(&(*root)->lchild);
                CreateBtree(&(*root)->rchild);
        }
}

void in(btree root)
{
        if(root)
        {
                in(root->lchild);
                printf("[%c ] ", root->data);
                in(root->rchild);
        }
}


void herit(btree root)
{
        printf("%c", root->data);
        if(root->lchild || root->rchild){
                printf("(");
                if(root->lchild)
                        herit(root->lchild);
                if(root->rchild)
                        herit(root->rchild);
                printf(")");
        }
}


int main(void)
{
        btree root;
        CreateBtree(&root);
        in(root);
        putchar('\n');

        herit(root);
        putchar('\n');
        printf(" \n######Wors*/k done!#######\n");

        return 0;
}


如何增加边界检测才能去掉多余的括号 ?求解！！

人造人 发表于 2018-6-25 18:02:15

如果可以，把代码发完整，我研究研究

Martine 发表于 2018-6-25 18:10:45

人造人 发表于 2018-6-25 18:02
如果可以，把代码发完整，我研究研究

测试数据　ＡＢE#F##CG##D###

人造人 发表于 2018-6-25 18:38:23



图片不对吧？

也就是说要输入 ABE#F##CG##D### ，输出 A(B(EF)C(G)D) 就行了？

Martine 发表于 2018-6-25 18:51:05

人造人 发表于 2018-6-25 18:38
图片不对吧？

也就是说要输入 ABE#F##CG##D### ，输出 A(B(EF)C(G)D) 就行了？

是！
要的就是你那种结果
你是怎么做到的?

人造人 发表于 2018-6-25 19:01:31

Martine 发表于 2018-6-25 18:51
是！
要的就是你那种结果
你是怎么做到的?

我复制了你的代码，就是那个截图
不是输入 ABE#F##CG##D###，输出 A(B(EF)C(G)D) 吗？
现在是输入 ABE#F##CG##D###，输出 A(B(E(F)C(GD)))

Martine 发表于 2018-6-25 19:17:44

人造人 发表于 2018-6-25 19:01
我复制了你的代码，就是那个截图
不是输入 ABE#F##CG##D###，输出 A(B(EF)C(G)D) 吗？
现在是输入 ABE# ...

错了，　答案是A(B(EF)C(G)D)　不是A(B(E(F)C(GD)))；
Ｄ的父节点是Ａ　不是Ｃ

人造人 发表于 2018-6-25 20:15:19

Martine 发表于 2018-6-25 19:17
错了，　答案是A(B(EF)C(G)D)　不是A(B(E(F)C(GD)))；
Ｄ的父节点是Ａ　不是Ｃ


貌似是对了？
我也不确定，这个结果是调试出来的，再换几组数据测试一下

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

typedef char ElemType;

typedef struct node
{
        ElemType data;
        struct node *lchild, *rchild;
}node, *btree;


char data[] = "ABE#F##CG##D###";
char *p = data;
void CreateBtree(btree *root)
{
        ElemType c;
        //scanf("%c", &c);
        c = *p++;                // 为 debug 方便

        if('#' == c){
                *root = NULL;
        }
        else{
                *root = (btree)malloc(sizeof(node));
                (*root)->data = c;

                CreateBtree(&(*root)->lchild);
                CreateBtree(&(*root)->rchild);
        }
}

void in(btree root)
{
        if(root)
        {
                in(root->lchild);
                printf("[%c ] ", root->data);
                in(root->rchild);
        }
}


void herit(btree root)
{
        printf("%c", root->data);
        if(root->lchild || root->rchild){
                if(root->lchild)
                        printf("(");

                if(root->lchild)
                        herit(root->lchild);
                if(root->rchild)
                        herit(root->rchild);
               
                //if(root->rchild)
                //        printf(")");
        }
        else
                printf(")");
}


int main(void)
{
        btree root;
        CreateBtree(&root);
        in(root);
        putchar('\n');

        herit(root);
        putchar('\n');
        printf(" \n######Wors*/k done!#######\n");

        return 0;
}

Martine 发表于 2018-6-26 09:12:33

人造人 发表于 2018-6-25 20:15
貌似是对了？
我也不确定，这个结果是调试出来的，再换几组数据测试一下

感谢！！！

Martine 发表于 2018-6-26 09:13:03

人造人 发表于 2018-6-25 20:15
貌似是对了？
我也不确定，这个结果是调试出来的，再换几组数据测试一下

感谢！！！
页: [1]
查看完整版本: 二叉树转化为森林 父子关系的递归遍历