数据结构C二叉树实验报告.doc

北 京 林 业 大 学12学年13学年第1学期数据结构实验报告书专 业：自动化 班 级：111 姓 名： 宁友菊 学 号： 111044120 实验地点： B2机房 任课教师： 孟伟 实验题目：二叉树的基本操作 实验环境： Visual C+ 实验目的：1掌握二叉树的定义；2掌握二叉树的基本操作，如建立、前序遍历、中序遍历和后序遍历、结点个数的统计等；实验内容：用递归的方法实现以下算法：1以二叉链表表示二叉树，建立一棵二叉树；2输出二叉树的前序遍历结果；3输出二叉树的中序遍历结果；4输出二叉树的后序遍历结果；5统计二叉树的叶结点个数；6统计二叉树的结点个数；7计算二叉树的深度。8交换二叉树每个结点的左孩子和右孩子；实现方法、实验结果及结论分析等：（一）实现方法1. 所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义） 实验采用二叉树的数据结构，以二叉链表存储，主程序中采用switch函数调用各个子程序以实现各个功能。0结束程序，输入错误时返回主函数重新输入。2. 自定义函数的名称及其功能说明 （1）void CreateBiTree 以二叉链表表示二叉树，建立一棵二叉树；（2）void PreOrderTraverse 输出二叉树的前序遍历结果；（3）void InOrderTraverse 输出二叉树的中序遍历结果；（4）void PostOrderTraverse 输出二叉树的后序遍历结果；（5）int LeafNodeCount 统计二叉树的叶结点个数；（6）int Node Count 统计二叉树的结点个数；（7）int Depth 计算二叉树的深度。（8）int Swap 交换二叉树每个结点的左孩子和右孩子；3. 主要功能算法void PreOrderTraverse的时间复杂度O（n）=O（n1)O(n2)O(n3)O(n4)O(n5)O(n6)O(n7)xO(n8)O（n1)void CreateBiTree函数算法时间复杂度O(n)O(n2)void PreOrderTraverse函数算法时间复杂度O(n)O(n3)void InOrderTraverse函数算法时间复杂度O(n)O(n4)void PostOrderTraverse 函数算法时间复杂度O(n)O(n5)int LeafNodeCount函数算法时间复杂度O(n)O(n6)int NodeCount函数算法时间复杂度O(n)O(n7)int Depth函数算法时间复杂度O(n) O(n8)int Swap 函数算法时间复杂度O(n)4. 实验流程图（2） 实验结果1、选择操作一：2、 创建二叉树3、 前序遍历结果4、 中序遍历结果5、 后序遍历结果6、 总结点数7、 叶节点数8、 二叉树深度9、 对换左右孩子10、 退出11、 输入错误检测（三）结论分析1. 问题与解决方法在编写程序时，遇到了一个程序保存后编译正确却运行不了，之后请教了我们班的同学，才知道是第一个函数出了问题，改了之后就好了。2. 收获和体会 做程序编写时，必须要细心，有时候问题出现了，可能会一直查不出来。自己也不容易发现。在编写这个程序时，我就出现了这个问题，之后一