二叉树的建立与遍历实验报告(c语言编写-附源代码)

第1页，共9页二叉树的建立与遍历实验报告级班年月日姓名学号_1．实验题目建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。2．需求分析本程序用VC编写，实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。①输入的形式和输入值的范围：输入二叉树的先序，当其结点为空时，需要输入#。（输入的先序仅含字母和#）②输出的形式：输出二叉树的先序、中序、后序。③程序所能达到的功能：实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。④测试数据：输入数据：输入ABC##DE#G##F###输出结果：二叉树的先序遍历为：ABCDEGF二叉树的中序遍历为：CBEGDFA二叉树的后序遍历为：CGEFDBA3．概要设计1)为了实现上述程序功能，需要定义二叉链表的抽象数据类型：typedefstructBinaryTreeNode{TElemTypedata;//二叉树结点中的数据域structBinaryTreeNode*lchild,*rchild;//二叉树结点的左孩子和右孩子指针}BinaryTreeNode,*BiTree;第2页，共9页基本操作：A.voidCreateBinaryTree(BiTree&T)初始条件：无操作结果：建立了二叉树。B.voidPreOrder(BiTreeT)初始条件：存在一棵二叉树操作结果：先序遍历二叉树，并且输出先序遍历的结果。C.voidMidOrder(BiTreeT)初始条件：存在一棵二叉树操作结果：中序遍历二叉树，并且输出中序遍历的结果。D.voidPostOrder(BiTreeT)初始条件：存在一棵二叉树操作结果：后序遍历二叉树，并且输出后序遍历的结果。程序包含5个函数：○1主函数main()○2先序建立二叉树voidCreateBinaryTree(BiTree&T)○3先序遍历二叉树，并且输出先序遍历的结果voidPreOrder(BiTreeT);○4中序遍历二叉树，并且输出中序遍历的结果voidMidOrder(BiTreeT);○5序遍历二叉树，并且输出后序遍历的结果voidPostOrder(BiTreeT);各函数间关系如下：主函数main()CreateBinaryTreePreOrderMidOrderPostOrder第3页，共9页4．详细设计1)二叉链表的定义typedefstructBinaryTreeNode{定义一个树结点的数据域;定义一个该结点的左孩子指针和右孩子指针;}2)voidCreateBinaryTree(BiTree&T)//先序建立二叉树{输入一个字符量;if(输入字符=='#')T指针置值为NULL;else{动态申请一个指向二叉树结构体的指针把输入字符赋值给新指针的数据域data;调用CreateBinaryTree(新指针的lchild成员);调用CreateBinaryTree(新指针的rchild成员);}}3)voidPreOrder(BiTreeT)//先序遍历二叉树{if(T指针不为NULL){输出T的data域;先序遍历左子树;先序遍历右子树;}}第4页，共9页4)voidMidOrder(BiTreeT)//中序遍历二叉树{if(T指针不为NULL){中序遍历左子树;输出T的data域;中序遍历右子树;}}5)voidPostOrder(BiTreeT)//中序遍历二叉树{if(T指针不为NULL){后序遍历左子树;后序遍历右子树;输出T的data域;}}5．调试分析在编写程序过程中，我将scanf（”%c”,&ch）中的%c写成%d，程序运行了一段时间没有结果，经过检查，发现了这个错误。编写程序不能有一点马虎，否则后续纠错工作很辛苦，编写程序的进度变慢。6．使用说明程序名为：二叉树遍历.exe，运行环境为DOS。程序执行后显示输入字符，先序建立二叉树：此时请输入一棵二叉树的先序，并且当结点为空时，输入#输入完成后，会输出该二叉树的先序遍历、中序遍历和后序遍历第5页，共9页7．测试结果1)输入数据：输入ABC##DE#G##F###输出结果：二叉树的先序遍历为：ABCDEGF二叉树的中序遍历为：CBEGDFA二叉树的后序遍历为：CGEFDBA2)输入数据：输入AB##C##输出结果：二叉树的先序遍历为：ABC二叉树的中序遍历为：BAC二叉树的后序遍历为：BCA3)二叉树如下：先序输入这棵二叉树，程序运行结果为：第6页，共9页程序源代码：#includestdio.h#includestdlib.htypedefcharTElemType;typedefstructBinaryTreeNode//二叉链表的存储结构{TElemTypedata;structBinaryTreeNode*lchild,*rchild;}BinaryTreeNode,*BiTree;voidCreateBinaryTree(BiTree&T)//先序建立二叉树{charch;scanf(%c,&ch);if(ch=='#')T=NULL;else{if(!(T=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode))))exit(-1);//判断malloc函数是否获得符合要求的内存块，是则继续程序，否则使用exit函数强制退出程序第7页，共9页//如果malloc函数无法获得符合要求的内存块，malloc函数会返回NULL指针T-data=ch;CreateBinaryTree(T-lchild);CreateBinaryTree(T-rchild);}}voidPreOrder(BiTreeT)//先序遍历二叉树{if(T){printf(%c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);}}voidMidOrder(BiTreeT)//中序遍历二叉树{if(T){MidOrder(T-lchild);第8页，共9页printf(%c,T-data);MidOrder(T-rchild);}}voidPostOrder(BiTreeT)//后序遍历二叉树{if(T){PostOrder(T-lchild);PostOrder(T-rchild);printf(%c,T-data);}}voidmain(){BiTreeTree;printf(输入字符，先序建立二叉树：\n);CreateBinaryTree(Tree);printf(二叉树的先序遍历为：\n);PreOrder(Tree);printf(\n二叉树的中序遍历为：\n);第9页，共9页MidOrder(Tree);printf(\n二叉树的后序遍历为：\n);PostOrder(Tree);getchar();getchar();}