二叉树的使用报告--数据结构（C语言）.doc

数据结构作业报告 姓名：江海强 班级：070921班 学号上机时间：2010-10-14 报告时间：2010-10-19 摘要 1.实验目的 此程序主要是让我们了解二叉树的链式结构的存储，理解二叉树的遍历过程，完成二叉树的创建序遍历、中序遍历、后序遍历Word绘出设计出其图形。 二．算法描述 本程序除了运用一些条件语句，判断语句，switch语句之外，主要运用了程序自身调用递归法。 XianXu()，ZhongXu()和HouXu()这三个子函数的复杂度都为O(N)，其中N为二叉树的结点个数。又XianXu()执行了两次，复杂度分别为O(N)和 O(N-2)，即总的时间复杂度为3×O(9) + O(7)。 CengCi()的复杂度为O(40)。 AoRu()的复杂度为3×O(9)+ O(16)，而AoRu()子函数执行了两次，故总的时间复杂度为6×O(9)+ 2×O(16)。 故所有输出型子函数的复杂度为：9×O(9)+ 2×O(16) + O(7)+ O(40)= O(160)。 由上述的二叉树图形结构图可以得知该二叉树的二叉树 先序遍历为:1、2、4、8、5、3、6、9、7。 中序遍历为:8、4、2、5、1、6、9、3、7。 后序遍历为:8、4、5、2、9、6、7、3、1。 层次遍历为:1、2、3、4、5、6、7、8、9。 此结果与下面的输出结果是一样的。 变换左右孩子之后的二叉树为右图②所示。 删除的结点也是从变换左右孩子之后的二叉树 中进行删除的。其中删除的结点为4和6。即为图③。 三．变量说明 其中typedef struct BiTree为二叉树的结构体。而lchild和rchild分别为二叉树结点的左右孩子。并且把变量a,b,c,d,e,f,g,h和i作为二叉树的9个结点，其权分别为1,2,3,4,5,6,7,8和9。 定义depth为静态变量，是二叉树的深度-1。depth会因为子函数AoRu()的调用次数而改变，而其对应着二叉树的输入结点的度-1。 定义数组A[4][10]为全局变量，是用来存放二叉树的结点的。因为该二叉树的深度为4,即是depth可为0,1,2和3,而数组A[4][10]根据depth把不同的度的结点分别存放在A[0][10]，A[1][10]，A[2][10]和A[3][10]上，从而实现层次遍历。 四．函数与思路说明 本程序包含1个主程序和9个子函数。其中输出型的子函数分别为XianXu()，ZhongXu()，HouXu()，CengCi()以及AoRu()；还有一些换算的子函数，如Exchange()，ChildNode()，ExchangeChild()以及Deletenode()。 子函数XianXu()，ZhongXu()和HouXu()，是对已经创建好的二叉树分别进行先序遍历输出，中序遍历输出和后序遍历输出。这三个子函数所使用的方法都是对自身进行调用的递归法。 CengCi()这个子函数是对二叉树进行层次遍历输出。利用之前已经把该二叉树的结点按照度的不同而存入到数组A[4][10]上，运用for语句输出数组A[4][10]，得出的数据即为原二叉树的层次遍历结果。 AoRu()这个子函数是对二叉树进行凹入遍历输出。利用了二叉树结点的度的特点和对自身调用的递归法实现对二叉树的凹入遍历输出。 子函数Exchange()的功能是交换两个数。而子函数ChildNode()的功能是判断二叉树结点的孩子的个数。最后ExchangeChild()这个子函数则是调用了Exchange()和ChildNode()，从而实现对二叉树左右孩子的调换。 Deletenode()这个子函数的功能是删除给定的结点子树。 五．程序执行结果 　　二叉树凹入法遍历结果: 1 |---2 　　|---4 　　|---8 　　 |---5 |---3 　　|---6 　　|---9 　　|---7 　　 二叉树先序遍历结果: 1 2 4 8 5 3 6 9 7 　　 二叉树中序遍历结果: 8 4 2 5 1 6 9 3 7 　　 二叉树后序遍历结果: 8 4 5 2 9 6 7 3 1 　　 二叉树层次遍历结果: 1 2 3 4 5 6 7 8 9 　　 交换左右子树后的二叉树的凹入法遍历结果: 1 |---3 　　|---5 　　|---8 　　|---4 |---2 　　|---7 　　|---9 　　|---6 　　 删除某些结点后的二叉树的先序遍