zyyAAA实验二-根据二叉树的抽象数据类型的定义-使用二叉链表实现一个二叉树

北京邮电大学信息通信工程学院数据结构实验报告实验名称：实验基于二叉树的抽象数据类型的定义，用二叉链表实现二叉树学生名称：郭江枫班级： 2017211125班内序列号： 10学位： 2017210722日期： 2018年5月24日1 .实验要求基于二叉树的抽象数据类型的定义，用二叉树表实现二叉树基本要求：基于二叉树的抽象数据类型的定义，用二叉树表实现二叉树。二叉树的基本功能：一、二叉树的制作2、按前面的顺序横穿二叉树3、中序横穿二叉树4、往后过二叉树5、按层次横穿二叉树求二叉树的深度7 .确定从指定节点到根的路径八、二叉树的破坏9、其他：自定义操作描述main ()函数测试线性表的正确性2 .程序分析2.1存储结构编码表的记忆结构：二叉树二叉链表的示例如下所示PSdatarch侧PSdatarch侧PSdatarch侧PSdatarch侧PSdatarch侧PSdatarch侧PSdatarch侧二叉树的节点结构：模板，模板，模板结构节点/定义节点举止T data； /数据节点* lch； /左子节点* rch； /右子2.2重要的算法分析为了实施这个项目，需要以下步骤步骤1 :创建二叉树步骤2 :前进第三步：逐次遍历步骤4 :向后退步骤5 :按层顺序遍历步骤6 :计算树的深度步骤7 :求出从指定节点到根的路径步骤8 :销毁二叉树步骤1 :从顺序存储结构和性质5可以看出，如果现在节点的位置是I，则左侧孩子的位置是2i，右侧孩子是2i 1。 因此，以顺序存储结构作为输入，建立根节点后，以建立左右孩子的方法递归地建立二叉树。模板，模板，模板创建void creat (节点* r，T data，int i，int n)/二叉树举止if (i=ndatai - 1)/个数据没有存储，数据不为空时举止r=新节点； /定义新节点R-data=datai - 1； 把第/i个数据提供给r的数据creat(R-lch，data，2 * i，n) /递归地创建左子树创建(r-rch，数据，2 * i 1，n) /递归地创建右子树以下else R=NULL； /不满足的话是空的以下步骤2 :由二叉树的引言扫描定义，与递归结合，写引言扫描的递归算法。模板，模板，模板void preorder(node*R)/序言遍历举止PS！ 如果=NULL)/不为空，请执行以下操作举止cout R-data； 输出/r的数据穿过preorder(R-lch) /左子树横过preorder(R-rch) /右子树以下以下步骤3 :用二叉树的中序遍历定义，结合递归，编写中序遍历的递归算法。模板，模板，模板void in order (节点* r )/中序遍历)举止PS！ 如果=NULL)/不为空，请执行以下操作举止渡过左子树(r-lch )/左子树cout R-data； 输出/r的数据跨越inorder(R-rch) /右子树以下以下步骤4 :用二叉树的后序遍历定义，结合递归，编写后序遍历的递归算法。模板，模板，模板void postorder(node*R)/后退导线举止PS！ 如果=NULL)/不为空，请执行以下操作举止穿过postorder(R-lch) /左子树横穿postorder(R-rch) /右子树cout R-data； 输出/r的数据以下以下步骤5 :进行层次顺序遍历时，在完成对某个层次的节点的访问后，按这些访问顺序依次访问各节点的左侧孩子和右侧孩子，则该层次在一个层次上进行，先访问的节点的左右孩子也先访问，这是队列的特性因此，我们能够利用队列来实现二叉链表的层序遍历。模板，模板，模板void level order (节点* r )/层序遍历)举止节点*队列 1000 ；int f=0，r=0； /初始化空队列PS！=NULL )queue r=R； /根节点入队PS！=r )举止节点* p=队列； /团队头目要素离开团队cout p-data； /输出队列标头元素PS (PR PS )！=NULL )queue r=p-lch； /如果左子树不为空，则将左子树元素入队PC (PR PR )！=NULL )队列=p-rch； /如果右子树不为空，则将右子树元素入队以下以下步骤6 :组合递归函数，依次扫描左右子树，每当某个节点的左右孩子空时返回他的深度，进行左右子树的比较，选择较大的数量作为树的深度模板，模板，模板计算int count(node*R)/树的深度举止if (R=NULL )返回0； /如果节点为空，则返回0else举止通过int m=count(R-lch) /左子树横跨int n=count(R-rch) /右子树return m=n？ m 1 : n 1； 返回/m和n的大树以下以下步骤7 :递归判断查找我们要查找的数据，如果找到，则返回true，并输出该数据。 使用bool函数来判断模板，模板，模板bool road (节点* r，toa )举止如果if (R=NULL)/为空，则为false返回假；如果if (R-data=a | road(R-lch，a) | road(R-rch，a)/的数据在a或r的左侧子树中存在a或r的右侧子树中，则执行以下步骤举止cout R-data； /打印路径上的节点标记返回真；以下返回假；以下步骤8 :二叉链表属于动态的记忆分配，必须用结构函数释放二叉链表的所有节点。 为了防止内存泄露，为了释放节点，采用释放该节点的左右子树，在左右子树全部释放后释放节点，以后进行巡视的方法模板，模板，模板销毁void releae(node*R)/二叉树举止PS！=NULL )举止releae(R-lch) /递归左子树releae(R-rch) /递归右子树删除r； /删除节点以下以下时间复杂度： O(n )空间复杂度： O(n2 )2.3其他该实验主要是递归和矩阵的应用，基于链表建立二叉树进行一系列操作。开始。3 .程序的执行结果制作二叉树。计算树的深度输入用户要检索的数据向前走中顺导线检索数据和打印路径层序遍历废弃二叉树。结束。测试