数据结构实习报告----二叉树

二叉树
一、需求分析
     1、设计任务
         建立一棵二叉树，数据以字符串形式从键盘输入。在此二叉树上完成：
 （1）前序、中序、后序遍历
（2）求出叶子数
（3）求树高二叉树
（4）左右子树交换，输出交换后的前序、中序遍历序列
 选做：
（1）给出非递归的后序遍历
（2）扩充为中序线索树，写出非递归的中序遍历
（3）在两个数组中分别有前序和中序遍历序列，试建立该二叉树
 2、输入的形式和输出值的范围
      二叉树 二叉树的建立：本程序的二叉树的建立函数时根据二叉树的前序排列生成的，但是其中子树为空地方用特殊符号“＊”代替。
       二叉树的输出值的范围：二叉树的输出是把二叉树各节点的值按遍历顺序输出的，本程序各节点的数据类型为字符型(可以在编译预处理修改)。
 3、输出的形式
       二叉树的输出是根据二叉树的遍历顺序输出的（包括前序、中序和后序三种）把各节点地值输出。 
 4、程序所能达到的功能
       本程序能够实现对二叉树的一些简单操作，例如二叉树的各种遍历(包括二叉树的前序、中序和后序的递归遍历以及非递归遍历)、求二叉树的叶子数和高以及二叉树的左右子树交换。