《算法与数据结构》课程
实
验
报
告
教师评阅意见：实验成绩：
签名：
年月日
f一、实验目的
1、实现二叉树的存储结构2、熟悉二叉树基本术语的含义3、掌握二叉树相关操作的具体实现方法
二、实验内容及要求
1建立二叉树2计算结点所在的层次3统计结点数量和叶结点数量4计算二叉树的高度5计算结点的度6找结点的双亲和子女7二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历8二叉树的复制9二叉树的输出等
三、系统分析
（1）数据方面：该二叉树数据元素采用字符char型，并且约定“”作为二叉树输入结束标识符。并在此基础上进行二叉树相关操作。（2）功能方面：能够实现二叉树的一些基本操作，主要包括：
1采用广义表建立二叉树。2计算二叉树高度、统计结点数量、叶节点数量、计算每个结点的度、结点所在层次。3判断结点是否存在二叉树中。4寻找结点父结点、子女结点。5递归、非递归两种方式输出二叉树前序、中序、后序遍历。6进行二叉树的复制。
四、系统设计
（1）设计的主要思路二叉树是的结点是一个有限集合，该集合或者为空，或者是由一个根节点加
上两棵分别称为左子树和右子树、互不相交的二叉树组成。根据实验要求，以及课上老师对于二叉树存储结构、基本应用的讲解，同时课后研究书中涉及二叉树代码完成二叉树模板类，并将所需实现各个功能代码编写完成，在建立菜单对功能进行调试。（2）数据结构的设计
f二叉树的存储结构有数组方式和链表方式。但用数组来存储二叉树有可能会消耗大量的存储空间，故在此选用链表存储，提高存储空间的利用率。根据二叉树的定义，二叉树的每一个结点可以有两个分支，分别指向结点的左、右子树。因此，二叉树的结点至少应包括三个域，分别存放结点的数据，左子女结点指针，右子女结点指针。这将有利于查找到某个结点的左子女与右子女，但要找到它的父结点较为困难。该实验采取二叉链表存储二叉树中元素，具体二叉树链表表示如下图所示。
（3）基本操作的设计
图1二叉树的链表表示
二叉树关键主要算法：
利用广义表进行二叉树的建立。该算法首先通过重载输入符号，在重载函数
中调用CreatBi
Tree函数，该函数有两个参数，第一个参数为输入流，用于传递
用户输入的二叉树字符串，第二个参数则是二叉树的根结点root。再通过栈操作
是实现二叉树。
递归与非递归两种方式实现前序、中序、后序的遍历。递归实现三种遍历的
函数均只有一个参数即二叉树根节点root，递归结束r