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

《数据结构C二叉树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京林业大学12学年—13学年第1学期数据结构实验报告书专业：自动化班级：11－1姓名：宁友菊学号：111044120实验地点：B2机房任课教师：孟伟实验题目：二叉树的基本操作实验环境：VisualC++实验目的：1．掌握二叉树的定义；2．掌握二叉树的基本操作，如建立、前序遍历、中序遍历和后序遍历、结点个数的统计等；实验内容：用递归的方法实现以下算法：1．以二叉链表表示二叉树，建立一棵二叉树；2．输出二叉树的前序遍历结果；3．输出二叉树的中序遍历结果；4．输出二叉树的后序遍历结果；5．统计二叉树的叶结点个数；6．统计二叉树的结点个数；7．计算二叉树的深度。

2、8．交换二叉树每个结点的左孩子和右孩子；实现方法、实验结果及结论分析等：（一）实现方法1.所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）实验采用二叉树的数据结构，以二叉链表存储，主程序中采用switch函数调用各个子程序以实现各个功能。0结束程序，输入错误时返回主函数重新输入。2.自定义函数的名称及其功能说明（1）voidCreateBiTree以二叉链表表示二叉树，建立一棵二叉树；（2）voidPreOrderTraverse输出二叉树的前序遍历结果；（3）voidInOrderTraverse输出二叉树的中序遍历结果；（4）voidP

3、ostOrderTraverse输出二叉树的后序遍历结果；（5）intLeafNodeCount统计二叉树的叶结点个数；（6）intNodeCount统计二叉树的结点个数；（7）intDepth计算二叉树的深度。（8）intSwap交换二叉树每个结点的左孩子和右孩子；2.主要功能算法voidPreOrderTraverse的时间复杂度O（n）=O（n1)×O(n2)×O(n3)×O(n4)×O(n5)×O(n6)×O(n7)xO(n8)O（n1)——voidCreateBiTree函数算法时间复杂度O(n)O(n2)——voidPreOrderTraver

4、se函数算法时间复杂度O(n)O(n3)——voidInOrderTraverse函数算法时间复杂度O(n)O(n4)——voidPostOrderTraverse函数算法时间复杂度O(n)O(n5)——intLeafNodeCount函数算法时间复杂度O(n)O(n6)——intNodeCount函数算法时间复杂度O(n)O(n7)——intDepth函数算法时间复杂度O(n)O(n8)——intSwap函数算法时间复杂度O(n)4.实验流程图（二）实验结果1、选择操作一：2、创建二叉树3、前序遍历结果4、中序遍历结果5、后序遍历结果2、总结点数3、叶节

5、点数4、二叉树深度2、对换左右孩子3、退出4、输入错误检测（三）结论分析1.问题与解决方法在编写程序时，遇到了一个程序保存后编译正确却运行不了，之后请教了我们班的同学，才知道是第一个函数出了问题，改了之后就好了。2.收获和体会做程序编写时，必须要细心，有时候问题出现了，可能会一直查不出来。自己也不容易发现。在编写这个程序时，我就出现了这个问题，之后一定要尽量避免此类问题出现。3.尚存在的问题这几个子函数的名称都是边看着书边写的，还没有完全脱离书本，真正变成自己建的东西。还要加强记忆。