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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。