二叉树实验报告

实验题目建立一棵用二叉链表方式存储的二

叉树，并进行遍历（先序、中序、后通工班内序号：学生姓名:一、 实验目的掌握用二叉链表创建二叉树；掌握对树的遍历，先序、中序、后序、层次，用递归和算法。二、 实验内容从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序、层次），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。例如：测试数据：ABC..DE.G.F…输出结果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA层次：ABCDEFG三、 数据结构及算法思想创建函数的思想：首先读入当前根结点的数据，如果是''，则将当前树根置为空，否则申请一个空结点，存入当前根结点的数据，分别用当前根结点的左子域和右子域进行递归调用，创建左右子树。二叉树的遍历方法是：按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次的过程。根据访问结点的顺序分为先序遍历、中序遍历和后序遍历先序遍历：访问根结点按先序遍历左子树；按先序遍历右子树；中序遍历：按中序遍历左子树；访问根结点；按中序遍历右子树；后序遍历：按后序遍历左子树；按后序遍历右子树；访问根结点；四、 模块划分对各个模块进行功能的描述voidGreateBiTree(BiTree*bt)〃建立二叉树voidPreOrder(BiTreeroot)//先序遍历voidInOrder(BiTreeroot)//中序遍历voidPostOrder(BiTreeroot)//后序遍历模块之间关系及其相互调用的，定义结构主函数先序遍历中序遍历后序遍历该树可以表示为:运用递归算法，以先序为例:五、详细设计及运行结果程序设计及编码，测试数据，运行结果测试数据：ABC..DE.G.F…输出结果：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA层次：ABCDEFG六、调试情况，设计技巧及体会这次试验让我对二叉树的遍历有了很好的了解，对于先序，中序，后序和层次遍历有了好的掌握。编写代码前，应简单的画一个二叉树，先弄清算法思想，在开始编程，应先对于各个模块进行设计，调试，消除错误，当所有模块都设计完成后，选择正确的变量把所有模块连接在一起，程序就设计完成，这样才不会出现太多的错误，编程完以后，出现错误要知道调试，以得到正确结果。附:代码#include<stdio.h>#include<stdlib.h>#include<string.h>#defineStack_Size50#defineMAXSIZE50typedefstructNode{chardata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;voidGreateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='')*bt二NULL;else{(*bt)=(BiTree)malloc(sizeof(BiTNode));(*bt)->data二ch;GreateBiTree(&((*bt)->LChild));GreateBiTree(&((*bt)->RChild));}}voidPreOrder(BiTreeroot){if(root!二NULL){printf("%c",root->data);PreOrder(root->LChild);PreOrder(root->RChild);}}voidInOrder(BiTreeroot){if(root!二NULL){InOrder(root->LChild);printf("%c",root->data);InOrder(root->RChild);}}voidPostOrder(BiTreeroot){if(root!二NULL){PostOrder(root->LChild);PostOrder(root->RChild);printf("%c",root->data);}}voidmain(){inti;BiTreeroot;printf("CreateBin_Tree;InputPreOrder:");GreateBiTree(&root);do{printf("\t**********select************\n");printf("\tl:PreOrderTraversal\n");printf("\t2:InOrderTraversal\n");printf("\t3:PostOrdertraversal\n");printf("\tO:Exit\n");printf("\t*******************************\n");scanf("%d"，&i);switch(i){case1:printf("PrintBin_treePreOrder:");PreOrder(root);break;case2:printf("PrintBin_TreeInOrder:");InOrder(root);break;cas