二叉树及其应用实验报告
一、实验目的
  1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。
  2.掌握用指针类型描述、访问和处理二叉树的运算。
  二、实验要求
  1.认真阅读和掌握本实验的程序。
  2.上机运行本程序。
  3.保存和打印出程序的运行结果，并结合程序进行分析。
  4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运
  行结果。
  三、实验内容
  1.输入字符序列，建立二叉链表。
  2.按先序、中序和后序遍历二叉树（递归算法）。
  3.按某种形式输出整棵二叉树。
  4.求二叉树的高度。
  5.求二叉树的叶节点个数。
  6.交换二叉树的左右子树。
  7.借助队列实现二叉树的层次遍历。
  8.在主函数中设计一个简单的菜单，分别调试上述算法。
  为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。另一种方法是主教材中介绍
的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。若当前数据不为“#”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。
  四、解题思路先序中序后序遍历二叉树
  1访问根结点，○2先序遍历左子树，○3先序遍历右子树1、先序遍历：○
  1中序遍历左子树，○2访问根结点，○3中序遍历右子树2、中序遍历：○
  1后序遍历左子树，○2后序遍历右子树，○3访问根结点3、后序遍历：○
  4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。