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