基于C语言的二叉树遍历

Hydra

发布日期: 2019-10-02 11:45:11 浏览量: 71
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、实验要求

1.1 实现功能

在采用链式存储结构存储的二叉树上,以bt指向根结点,p指向任一给定的结点,编程实现求出从根结点bt到给定结点p之间的路径。

1.2 设计要求

  1. typedef struct node{
  2. char data; //数据域
  3. struct node *lchild , *rchild; //左右孩子指针
  4. }BinTNode, *BinTree; //树中结点类型

首先设计一个含有多个菜单项的主控菜单程序,然后再为这些菜单项配上相应的功能。

程序运行后,给出如下菜单项的内容和输入提示,使用数字0—7来选择菜单项,其它输入则不起作用:

  • 1.建立二叉树存储结构

  • 2.输出二叉树的形态

  • 3.求二叉树的先序遍历

  • 4.求二叉树的中序遍历

  • 5.求二叉树的后序遍历

  • 6.求二叉树的层次遍历

  • 7.求给定结点的路径

  • 0.退出系统

二、实验步骤

2.1 程序流程图

2.1.1 主函数流程图

2.1.2 CreateBiTree函数流程图

2.1.3 PreOrderTraverse函数流程图

2.1.4 InOrderTraverse函数流程图

2.1.5 PostOrderTraverse函数流程图

2.1.6 LevelOrderTraverse函数流程图

2.1.7 Path函数流程图

2.2 主函数源代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX 100 //队列最大长度
  5. typedef struct node{
  6. char data; //数据域
  7. struct node *lchild , *rchild; //左右孩子指针
  8. }BinTNode, *BinTree; //树中结点类型
  9. typedef struct
  10. {
  11. BinTree* base;
  12. int front;
  13. int rear;
  14. }Quene; //队列结构
  15. void CreateBiTree(BinTree &bt); //建立二叉树存储结构
  16. void OutputBiTree(BinTree bt); //输出二叉树的形态
  17. void PreOrderTraverse(BinTree bt); //求二叉树的先序遍历
  18. void InOrderTraverse(BinTree bt); //求二叉树的中序遍历
  19. void PostOrderTraverse(BinTree bt); //求二叉树的后序遍历
  20. void LevelOrderTraverse(BinTree bt); //求二叉树的层次遍历
  21. void Path(BinTree T, BinTree bt, char data, char* path, int &i); //求给定结点的路径
  22. void InitQuene(Quene &q); //创建队列
  23. int LengthQuene(Quene q); //计算队列长度
  24. void EnQuene(Quene &q, BinTree e); //进队
  25. void DeQuene(Quene &q, BinTree* e); //出队
  26. void getQuene(Quene q, BinTree* e);
  27. void printSpace(int n); //打印n个空格
  28. void main()
  29. {
  30. BinTree bt;
  31. while(1)
  32. {
  33. int choice;
  34. printf("请选择功能:\n");
  35. printf("1.建立二叉树存储结构\t2.输出二叉树的形态\n");
  36. printf("3.求二叉树的先序遍历\t4.求二叉树的中序遍历\n");
  37. printf("5.求二叉树的后序遍历\t6.求二叉树的层次遍历\n");
  38. printf("7.求给定结点的路径\t0.退出系统\n");
  39. scanf("%d", &choice);
  40. switch(choice)
  41. {
  42. case 1:
  43. getchar();
  44. CreateBiTree(bt);
  45. break;
  46. case 2:
  47. OutputBiTree(bt);
  48. break;
  49. case 3:
  50. PreOrderTraverse(bt);
  51. break;
  52. case 4:
  53. InOrderTraverse(bt);
  54. break;
  55. case 5:
  56. PostOrderTraverse(bt);
  57. break;
  58. case 6:
  59. LevelOrderTraverse(bt);
  60. break;
  61. case 7:
  62. {
  63. printf("请输入要查找的节点数据:");
  64. char ch;
  65. getchar();
  66. scanf("%c", &ch);
  67. char path[50]; //用于存储路径(倒置),最后倒置输出path
  68. BinTree T = bt;
  69. int i = 0;
  70. Path(T, bt, ch, path, i);
  71. printf("从根结点到达该结点的路径为:");
  72. for (int j = i - 1; j >= 0; --j)
  73. {
  74. printf("%c", path[j]);
  75. }
  76. break;
  77. }
  78. case 0:
  79. return;
  80. default:
  81. printf("输入数字错误\n");
  82. }
  83. printf("\n");
  84. }
  85. }

2.3 运行结果截图

2.3.1 主函数运行结果

2.3.2 CreateBiTree函数运行结果

2.3.3 PreOrderTraverse函数运行结果

2.3.4 InOrderTraverse函数运行结果

2.3.5 PostOrderTraverse函数运行结果

2.3.6 LevelOrderTraverse函数运行结构果

2.3.7 Path函数运行结果

三、总结与体会

在这几节实验课上,让我有机会将理论课上的一些知识真正地运用起来,将课本上的伪代码实现为C语言代码。通过这些实验题目,让我感受到理论知识和实际应用还是有一些区别,在学习数据结构的过程中,光学习理论知识是不够的,更重要的是自己动手实践,这样才能更好的理解知识并学会运用。

该实验让我更好地理解了二叉树三种遍历的递归实现和层次遍历的原理。在完成这这个程序的过程中也遇到一些困难,二叉树不会寻找搜索路径。在遇到问题时我回顾了课堂上讲的内容,并充分利用VC6.0的调试功能,最终独立解决了这些问题。

上传的附件 cloud_download 基于C语言的二叉树遍历.7z ( 509.46kb, 1次下载 )
error_outline 下载需要6点积分

发送私信

希望从来不会放弃你,是你放弃了希望

15
文章数
23
评论数
最近文章
eject