数据结构二叉树实验报告

实验三 二叉树的遍历一、实验目的１、熟悉二叉树的结点类型和二叉树的基本操作。２、掌握二叉树的前序、中序和后序遍历的算法。3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。二、实验环境运行Ｃ或 VC++的微机。三、实验内容1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。四、设计思路对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求2．二叉树采用动态数组3.二叉树运用 9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点五、程序代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0typedefstructTNode//{

结构体定义intdata;// 数据域structTNode*lchild,*rchild;//

指针域包括左右孩子指针}TNode,*Tree;voidCreateT(Tree*T)//

创建二叉树按

,依次输入二叉树中结点的值{inta;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));//

递归调用函数，构造左子树递归调用函数，构造右子树}}voidInitT(Tree*T)//{

构建空二叉树T=NULL;}voidDestroyT(Tree*T)//{

销毁二叉树if(*T)//{

二叉树非空DestroyT(&((*T)->lchild));//DestroyT(&((*T)->rchild));//free(T);T=NULL;

递归调用函数，销毁左子树递归调用函数，销毁右子树}}voidvisit(inte)//{

访问结点printf("%d",e);}voidPreOrderT(Tree*T,void(*visit)(int))//

先序遍历

T{if(*T)//{

二叉树非空visit((*T)->data);//

先访问根结点PreOrderT(&((*T)->lchild),visit);//PreOrderT(&((*T)->rchild),visit);//

递归调用函数，先序遍历左子树递归调用函数，先序遍历右子树}}voidInOrderT(Tree*T,void(*visit)(int)){if(*T){InOrderT(&((*T)->lchild),visit);//

递归调用函数，中序遍历左子树visit((*T)->data);//

访问根结点InOrderT(&((*T)->rchild),visit);//

递归调用函数，中序遍历右子树}}voidPostOrderT(Tree*T,void(*visit)(int)){if(*T){PostOrderT(&((*T)->lchild),visit);//PostOrderT(&((*T)->rchild),visit);//visit((*T)->data);// 访问根结点

递归调用函数递归调用函数

,后序遍历左子树,序遍历右子树}}voidexample(){inti;printf("

如果你想建立如图所示的二叉树

\n");printf("\n");printf("printf("printf("printf("printf("

4

/

3

1/ \\\\5

3

\\

7

\n");\n");\n");\n");\n");printf("\n");printf("

请输入：

13400005000030070000\n");printf("\n

按先序次序输入二叉树中结点的值

(

输入

00表示节点为空

)\n");for(i=0;i<71;i++)printf("*");printf("\n");}intmain(){TreeT;printf("************** 欢迎使用！ ************** 潘俊达\n");example();printf("\n 请输入所要建立的二叉树 :\n");CreateT(&T);InitT(&T);inti;printf(" 先序遍历二叉树： \n");PreOrderT(&T,visit);printf("\n");printf("\n 中序遍历二叉树： \n");InOrderT(&T,visit);printf("\n");printf("\n 后序遍历二叉树： \n");