数据结构实验报告三二叉树.docx

《数据结构实验报告三二叉树.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告实验名称：实验四题目1用二叉链表实现一个二叉树学生姓名：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿班级：2013211128＿＿＿＿＿＿＿＿＿＿＿＿＿＿班内序号：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿学号：2013210771＿＿＿＿＿＿＿＿＿＿＿＿＿＿日期：2014/12/05＿＿＿＿＿＿＿＿＿＿＿＿＿＿1.实验目的掌握二叉树基本操作的实现方法根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按

2、层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试二叉树的正确性2.程序分析2.1存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T类型的指针右孩子。在对二叉树的关键算法的实现过程中，采用了队列的存储结构。对于二叉树中每个结点的data域的赋值，我们事先把这些data储存在一个数组中，通过对数组元素的调用事先对二叉树中每个

3、结点的data域的赋值。2.2关键算法分析2.2.1二叉树的建立：A．自然语言描述：1首先判断调用的数组是否为空，如果为空，直接将一个已经初始化好的根节点置为空。2如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data域。3采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。完成对左右子树的赋值。时间复杂度：O（1）B．代码详细分析：templatevoidBitree::create(Binode*&R,Tdata[],inti)//创建二叉树{

4、if(data[i-1]!=0){R=newBinode;//创建根结点R->data=data[i-1];R->lch=R->rch=NULL;create(R->lch,data,2*i);//创建左子树create(R->rch,data,2*i+1);//创建右子树}}templateBitree::Bitree(Tdata[]){create(root,data,1);//createroot}2.2.2前序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：

5、输出它的data域3：遍历左子树4：遍历右子树时间复杂度：O（1）B.代码详细分析：templatevoidBitree::preorder(Binode*R)//前序遍历{if(R!=NULL){cout<data;//访问结点preorder(R->lch);//遍历左子树preorder(R->rch);//遍历右子树}}2.2.3中序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：遍历左子树3：访问结点4：遍历右子树时间复杂度：O（1）B.代码详细分

6、析：templatevoidBitree::Inorder(Binode*R)//中序遍历{if(R!=NULL){Inorder(R->lch);//遍历左子树cout<data;//访问结点Inorder(R->rch);//遍历右子树}}2.2.4后序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：遍历左子树3：遍历右子树4：访问结点时间复杂度：O（1）B.代码详细分析：templatevoidBitree::Postorder(

7、Binode*R)//后序遍历{if(R!=NULL){Postorder(R->lch);//遍历左子树Postorder(R->rch);//遍历右子树cout<data;//访问结点}}2.2.5层序遍历二叉树：A.自然语言描述：1：初始化空队列2：根结点入队3：队头元素出队4：出队打印5：左孩子入队6：右孩子入队时间复杂度：O（1）B.代码详细分析：templatevoidBitree::Levelorder(Binode*R)//层序遍历{Binod

8、e*queue[10000];intf=0,r=0;//初始化空队列if(R!=NULL)queue[++r]=R;//根结点入队while(f!=r){Binode*p=queue[++f];//队头元素出队cout<data;//出队打印if(p->lch!=NULL)queue[++r]=p->lch;//左孩子入队if(p->rch!=NULL)queue[++r]=p->rch;//右孩子入队}}2.2.6求二叉树的深度：时