设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 二叉树转化为森林 父子关系的递归遍历
返回列表 发新帖
查看: 3253|回复: 9

[已解决]二叉树转化为森林 父子关系的递归遍历

[复制链接]
Martine
发表于 2018-6-25 17:52:58 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

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

题:将如图所示的深林转化为二叉树(易)
pic2.png pic1.png
将父子关系表示为 父(子,子......)
则该森林的数据结构可以表示为 A(B(EF)C(G)D)

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

  4. typedef char ElemType;

  6. typedef struct node
  7. {
  8.         ElemType data;
  9.         struct node *lchild, *rchild;
  10. }node, *btree;

  12. void CreateBtree(btree *root)
  13. {       
  14.         ElemType c;
  15.         scanf("%c", &c);
  16.         if('#' == c){
  17.                 *root = NULL;
  18.         }else{
  19.                 *root = (btree)malloc(sizeof(node));
  20.                 (*root)->data = c;

  22.                 CreateBtree(&(*root)->lchild);
  23.                 CreateBtree(&(*root)->rchild);
  24.         }
  25. }

  27. void in(btree root)
  28. {
  29.         if(root)
  30.         {
  31.                 in(root->lchild);
  32.                 printf("[%c ] ", root->data);
  33.                 in(root->rchild);
  34.         }
  35. }


  38. void herit(btree root)
  39. {
  40.         printf("%c", root->data);
  41.         if(root->lchild || root->rchild){
  42.                 printf("(");
  43.                 if(root->lchild)
  44.                         herit(root->lchild);
  45.                 if(root->rchild)
  46.                         herit(root->rchild);
  47.                 printf(")");
  48.         }
  49. }


  52. int main(void)
  53. {
  54.         btree root;
  55.         CreateBtree(&root);
  56.         in(root);
  57.         putchar('\n');

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

  63.         return 0;
  64. }
复制代码

output.png

如何增加边界检测才能去掉多余的括号 ?求解！！
最佳答案
月排行榜 / 总排行榜
人造人
2018-6-25 20:15:19
Martine 发表于 2018-6-25 19:17
错了，　答案是A(B(EF)C(G)D)　不是A(B(E(F)C(GD)))；
Ｄ的父节点是Ａ　不是Ｃ

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

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

  4. typedef char ElemType;

  6. typedef struct node
  7. {
  8.         ElemType data;
  9.         struct node *lchild, *rchild;
  10. }node, *btree;


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

  21.         if('#' == c){
  22.                 *root = NULL;
  23.         }
  24.         else{
  25.                 *root = (btree)malloc(sizeof(node));
  26.                 (*root)->data = c;

  28.                 CreateBtree(&(*root)->lchild);
  29.                 CreateBtree(&(*root)->rchild);
  30.         }
  31. }

  33. void in(btree root)
  34. {
  35.         if(root)
  36.         {
  37.                 in(root->lchild);
  38.                 printf("[%c ] ", root->data);
  39.                 in(root->rchild);
  40.         }
  41. }


  44. void herit(btree root)
  45. {
  46.         printf("%c", root->data);
  47.         if(root->lchild || root->rchild){
  48.                 if(root->lchild)
  49.                         printf("(");

  51.                 if(root->lchild)
  52.                         herit(root->lchild);
  53.                 if(root->rchild)
  54.                         herit(root->rchild);
  55.                
  56.                 //if(root->rchild)
  57.                 //        printf(")");
  58.         }
  59.         else
  60.                 printf(")");
  61. }


  64. int main(void)
  65. {
  66.         btree root;
  67.         CreateBtree(&root);
  68.         in(root);
  69.         putchar('\n');

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

  75.         return 0;
  76. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2018-6-25 18:02:15 | 显示全部楼层
如果可以，把代码发完整，我研究研究
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

Martine
 楼主| 发表于 2018-6-25 18:10:45 | 显示全部楼层
人造人 发表于 2018-6-25 18:02
如果可以，把代码发完整，我研究研究

测试数据　ＡＢE#F##CG##D###
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2018-6-25 18:38:23 | 显示全部楼层
1.png

图片不对吧？

也就是说要输入 ABE#F##CG##D### ，输出 A(B(EF)C(G)D) 就行了？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

Martine
 楼主| 发表于 2018-6-25 18:51:05 | 显示全部楼层
人造人 发表于 2018-6-25 18:38
图片不对吧？

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

是！
要的就是你那种结果
你是怎么做到的?
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 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)))
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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)))；
Ｄ的父节点是Ａ　不是Ｃ
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2018-6-25 20:15:19 | 显示全部楼层    本楼为最佳答案   
Martine 发表于 2018-6-25 19:17
错了，　答案是A(B(EF)C(G)D)　不是A(B(E(F)C(GD)))；
Ｄ的父节点是Ａ　不是Ｃ

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

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

  4. typedef char ElemType;

  6. typedef struct node
  7. {
  8.         ElemType data;
  9.         struct node *lchild, *rchild;
  10. }node, *btree;


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

  21.         if('#' == c){
  22.                 *root = NULL;
  23.         }
  24.         else{
  25.                 *root = (btree)malloc(sizeof(node));
  26.                 (*root)->data = c;

  28.                 CreateBtree(&(*root)->lchild);
  29.                 CreateBtree(&(*root)->rchild);
  30.         }
  31. }

  33. void in(btree root)
  34. {
  35.         if(root)
  36.         {
  37.                 in(root->lchild);
  38.                 printf("[%c ] ", root->data);
  39.                 in(root->rchild);
  40.         }
  41. }


  44. void herit(btree root)
  45. {
  46.         printf("%c", root->data);
  47.         if(root->lchild || root->rchild){
  48.                 if(root->lchild)
  49.                         printf("(");

  51.                 if(root->lchild)
  52.                         herit(root->lchild);
  53.                 if(root->rchild)
  54.                         herit(root->rchild);
  55.                
  56.                 //if(root->rchild)
  57.                 //        printf(")");
  58.         }
  59.         else
  60.                 printf(")");
  61. }


  64. int main(void)
  65. {
  66.         btree root;
  67.         CreateBtree(&root);
  68.         in(root);
  69.         putchar('\n');

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

  75.         return 0;
  76. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

Martine
 楼主| 发表于 2018-6-26 09:12:33 | 显示全部楼层
人造人 发表于 2018-6-25 20:15
貌似是对了？
我也不确定，这个结果是调试出来的，再换几组数据测试一下

感谢！！！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

Martine
 楼主| 发表于 2018-6-26 09:13:03 | 显示全部楼层
人造人 发表于 2018-6-25 20:15
貌似是对了？
我也不确定，这个结果是调试出来的，再换几组数据测试一下

感谢！！！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-18 10:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表