树和二叉树实验报告

《树和二叉树实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、word格式树和二叉树一、实验目的1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2.掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求1.认真阅读和掌握本实验的程序。2.上机运行本程序。3.保存和打印出程序的运行结果，并结合程序进行分析。4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、实验内容1.输入字符序列，建立二叉链表。2.按先序、中序和后序遍历二叉树（递归算法）。3.按某种形式输出整棵二叉树。4.求二叉树的高度。5.求二叉树的叶节点个数。6.交换二叉树的左右子树。7.借助队列实现

2、二叉树的层次遍历。8.在主函数中设计一个简单的菜单，分别调试上述算法。为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。四、解

3、题思路1、先序遍历：访问根结点，先序遍历左子树，先序遍历右子树2、中序遍历：中序遍历左子树，访问根结点，中序遍历右子树3、后序遍历：后序遍历左子树，后序遍历右子树，访问根结点4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。五、程序清单#include#include#defineM100....word格式typ

4、edefcharEtype;//定义二叉树结点值的类型为字符型typedefstructBiTNode//树结点结构{Etypedata;structBiTNode*lch,*rch;}BiTNode,*BiTree;BiTreeque[M];intfront=0,rear=0;//函数原型声明BiTNode*creat_bt1();BiTNode*creat_bt2();voidpreorder(BiTNode*p);voidinorder(BiTNode*p);voidpostorder(BiTNode*p);voidenqueu

5、e(BiTree);BiTreedelqueue();voidlevorder(BiTree);inttreedepth(BiTree);voidprtbtree(BiTree,int);voidexchange(BiTree);intleafcount(BiTree);voidpaintleaf(BiTree);BiTNode*t;intcount=0;//主函数voidmain(){charch;intk;do{printf("");printf("===================主菜单===========

6、========");printf("1.建立二叉树方法1");printf("2.建立二叉树方法2");printf("3.先序递归遍历二叉树");printf("4.中序递归遍历二叉树");printf("5.后序递归遍历二叉树");printf("6.层次遍历二叉树");printf("7.计算二叉树的高度");printf("8.计算二叉树中叶结点个数");printf("9.交换二叉树的左右子树");printf("10.打印二叉树");prin

7、tf("0.结束程序运行");....word格式printf("============================================");printf("请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");scanf("%d",&k);switch(k){case1:t=creat_bt1();break;//调用性质5建立二叉树算法case2:printf("请输入二叉树各结点值:");fflush(stdin);t=creat_bt2();break;//调用递归建立二叉树

8、算法case3:if(t){printf("先序遍历二叉树:");preorder(t);printf("");}elseprintf("二叉树为空!");break;case4:if(t){printf("中序