实验四 二叉树的操作及应用实验学时：4实验类型：（设计型）一、实验目的1.理解并掌握二叉树的逻辑结构和物理结构——二叉链表；2.掌握二叉树的遍历方法； 3.掌握二叉树的构造方法；4. 掌握计算二叉树结点个数、高度、叶子结点个数算法实现； 5. 掌握交换二叉树左右子树以及复制一棵二叉树算法的实现。二、实验条件Visual C++ 6.0三、实验原理及相关知识1.二叉树的存储结构描述；2.二叉树中序、前序、后序、层次遍历的基本思想；3.构造二叉树的基本思想；4.求二叉树结点个数、高度、叶子结点个数算法的基本思想；5.交换二叉树左右子树以及复制一棵二叉树算法的基本思想。四、实验步骤1.确定存储结构，写出二叉链表结构类型的具体定义。2.基本操作的算法实现(1)中序、前序、后序、层次遍历的递归算法的基本思想及算法实现；(2)利用先序序列构造二叉树方法的基本思想及算法实现；(3)求结点个数、高度、叶子结点个数、交换二叉树左右子树以及复制一棵二叉树的递归算法的基本思想及算法实现。五、思考题及其它1.线索二叉树的构造及线索化方法的算法实现。【参考程序 1】#include#include#include #define MaxSize 20typedef int ElemType;#define OK 1typedef struct BiTNode{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;//建立二叉树（按先序序列生成二叉树,#表示空节点）void CreateBiTree(BiTree *T){char ch;scanf("%c",&ch);getchar();/*回车键（每次输入一个字符后，需敲回车键）*/if(ch=='#'){printf("不产生子树。\n");*T=NULL;}else{if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))){printf("分配空间失败");return;}//生成一个新节点(*T)->data = ch;printf("产生左右子树。\n"); ; ; }}//递归前序遍历void Preorder(BiTNode *T) { if(T) { printf("%c ",T->data); Preorder(T->lchild); Preorder(T->rchild); }}//递归中序遍历void Inorder(BiTNode *T){ if(T) { ; ; ; } }//递归后序遍历void Postorder(BiTNode *T){if(T){ ; ; ;} }//层次遍历二叉树void Translever(BiTNode *T){struct node{BiTNode *vec[MaxSize];int f,r; //r 为队尾，f 为队头}queue;BiTNode *p;p=T;queue.f=0;queue.r=0;if(T)printf("%c ", p->data);queue.vec[queue.r]=p;queue.r=queue.r+1;while(queue.f
