数据结构二叉实验报告.docVIP

实验三　二叉树的遍历 一、实验目的 １、熟悉二叉树的结点类型和二叉树的基本操作。 ２、掌握二叉树的前序、中序和后序遍历的算法。 3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 运行Ｃ或VC++的微机。 三、实验内容 1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。 2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。 四、设计思路 1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求 2．二叉树采用动态数组 3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点 五、程序代码 #include stdio.h #include stdlib.h #include malloc.h #define OK 1 #define ERROR 0 typedef struct TNode//结构体定义 { int data; //数据域 struct TNode *lchild,*rchild; // 指针域包括左右孩子指针 }TNode,*Tree; void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值 { int a; scanf(%d,a); if(a==00) // 结点的值为空 *T=NULL; else // 结点的值不为空 { *T=(Tree)malloc(sizeof(TNode)); if(!T) { printf(分配空间失败！！TAT); exit(ERROR); } (*T)-data=a; CreateT(((*T)-lchild)); // 递归调用函数，构造左子树 CreateT(((*T)-rchild)); // 递归调用函数，构造右子树 } } void InitT(Tree *T)//构建空二叉树 { T=NULL; } void DestroyT(Tree *T)//销毁二叉树 { if(*T) // 二叉树非空 { DestroyT(((*T)-lchild)); // 递归调用函数，销毁左子树 DestroyT(((*T)-rchild)); // 递归调用函数，销毁右子树 free(T); T=NULL; } } void visit(int e)//访问结点 { printf(%d ,e); } void PreOrderT(Tree *T,void(*visit)(int))//先序遍历T { if(*T) // 二叉树非空 { visit((*T)-data); // 先访问根结点 PreOrderT(((*T)-lchild),visit); // 递归调用函数，先序遍历左子树 PreOrderT(((*T)-rchild),visit); // 递归调用函数，先序遍历右子树 } } void InOrderT(Tree *T,void(*visit)(int)) { if(*T) { InOrderT(((*T)-lchild),visit); // 递归调用函数，中序遍历左子树 visit((*T)-data); // 访问根结点 InOrderT(((*T)-rchild),visit); // 递归调用函数，中序遍历右子树 } } void PostOrderT(Tree *T,void(*visit)(int)) { if(*T) { PostOrderT(((*T)-lchild),visit); // 递归调用函数,后序遍历左子树 PostOrderT(((*T)-rchild),visit); // 递归调用函数,序遍历右子树 visit((*T)-data); // 访问根结点 } } void example() { int i; printf(如果你想建立如图所示的二叉树\n); printf(\n); printf( 1 \n); printf(