实验一约瑟夫环问题.docx

数据结构课程实验指导书- 1- 实验报告部分 HUNAN UNIVERSITY 课程实习报告题目: 二叉树的实现学生姓名赵庆磊学生学号 201508010525 专业班级计科 1505 指导老师李晓鸿完成日期 数据结构课程实验指导书- 2- 一、需求分析(1 )、建立一棵二叉树; (2 )、实现二叉树的四种遍历操作; (3 )、对储存的二叉树进行查找操作,并输出该节点的父节点,子节点(左孩子, 右孩子)。(4 )、计算出二叉树的高度和节点数。二、概要设计抽象数据类型二叉树是 n(n ≥ 0) 个结点的有限集,它或者是空集(n=0) ,或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。所以可以用二叉链表来实现二叉树。算法的基本思想(1) 、基于前序遍历的查找方式, 并对其算法进行一些修改, 然后将二叉树储存到链表中, (2) 、前序遍历,先访问节点,然后访问其子节点; (3) 、后序遍历,先访问节点的子节点(包括他们的子树),再访问该节点; (4) 、中序遍历, 先访问左子节点( 包括整棵子树), 然后访问该节点, 再访问右子节点(包括整棵子树); (5) 程序的流程程序由三个模块组成: (1) 输入模块: 完成对二叉树元素的输入,将输入结果储存在二叉链表中。计算模块: 设计四个算法, 链表中的元素作为参数, 四个算法分别实现对二叉树的前序遍历, 中序遍历, 后序遍历, 层序遍历等基本操作。(2) 输出模块:屏幕上显示对二叉树遍历以后的结果,树的高度,节点数,要查找的节点的父节点,子节点。三、详细设计物理数据类型二叉树除了根节点没有前驱和叶节点没有后继之外, 其余节点均有一个前驱和一个以上的后继,所以二叉树不具有线性关系,就可以用二叉链( int 型)表来实现二叉树的储存。算法的具体步骤通过构造函数创建一个二叉树,构造函数通过调用函数 Create(BiNode<T>* &R,T data[],inti,int n) 创建二叉树,伪代码: 1. 定义根指针,输入节点储存的 data ,若输入“#”,则该节点为空; 2. 申请一个新节点, 判断它的父结点是否不为空, 如果不为空在判断其为左或者右孩子,并把地址付给父结点,把 data 写入。 voidBiTree<T>::Create(BiNode<T>* &R,T data[],inti,int n){ if(i<=n){ R=new BiNode<T>; R->data=data[i-1]; Create(R->lch,data,2*i,n); 数据结构课程实验指导书- 3- Create(R->rch,data,2*i+1,n); } else R=NULL; } 前序遍历 voidBiTree<T>::PreOrder(BiNode<T> *R) { BiNode<T>* S[100]; int top=-1; while((R!=NULL)||(top!=-1)){ if(R!=NULL){ cout<<R->data; S[++top]=R; R=R->lch; } else{ R=S[top--]; R=R->rch; }}} 中序遍历伪代码; 1. 设置递归边界条件: if root==null 则停止递归 2. 递归遍历左子树 3. 打印根节点数据域内 4. 递归遍历右子 voidBiTree<T>::InOrder(BiNode<T>* R){ if(R!=NULL){ InOrder(R->lch); cout<<R->data; InOrder(R->rch); }} 后序遍历伪代码: 1. 设置递归边界条件: if root==null 则停止递归 2. 递归遍历左子树 3. 递归遍历右子树 4. 访问根结点数据域 voidBiTree<T>::PostOrder(BiNode<T> *R) { if(R!=NULL){ PostOrder(R->lch); PostOrder(R->rch); cout<<R->data; }} 数据结构课程实验指导书- 4- 层序遍历 1. 队列 Q 及所需指针的定义和初始化 2. 如果二叉树非空,将根指针入 3. 循环直到队列 Q为 voidBiTree<T>::LevelOrder(BiNode<T> *R) { BiNode<T>* queue[9]; int f=0,r=0; if(R!=NULL) queue[++r]=R; while(f!=r){ BiNode<T> *p=queue[++f]; cout<<p->data; if(p->lch!=NULL) queue[++r]=p->lch; if(p->rch!=NULL) queue[++r]=p-