1、实验四 二叉树的基本操作一、实验目的： （1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； （2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想； （3）掌握二叉树和叶子数、深度之间的关系及联系。
2、二、实验内容： 构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。
3、三、实验步骤： (一) 需求分析 1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。 2．程序的执行命令为： 1）构造结点类型，然后创建二叉树。 2）根据提示，从键盘输入各个结点。 3）通过选择一种方式（先序、中序或者后序）遍历。 4）输出结果，结束。 (二)概要设计 1.二叉树的二叉链表结点存储类型定义 typedef struct Node { DataType data; struct Node *LChild; struct Node *RChild; }BitNode,*BitTree; 2.建立如图所示二叉树： 3.本程序包含六个模块 1) 主程序模块 2)先序遍历模块 3)中序遍历模块 4)后序遍历模块 5）叶子数模块 6）深度模块
4、四、测试结果 1. 进入演示程序后的显示主界面： 请输入二叉树中的元素； 先序、中序、后序遍历和叶子数、深度分别输出结果。 2.测试结果 以扩展先序遍历序列输入，其中#代表空子树：ABC##DE#G##F### 先序遍历序列为：ABCDEGF 中序遍历序列为：CBEGDFA 后序遍历序列为：CGEFDBA 此二叉树的叶子数为：3 此二叉树的深度为：5 3.程序运行结果截图：
5、五、源代码拭貉强跳#include#include//节点声明，数据域、左孩子指针、右孩子指针typedef struct BiTNode{ char data; stru艘早祓胂ct BiTNode *lchild,*rchild;}BiTNode,*BiTree; //先序建立二叉树BiTree CreateBiTree(){ char ch;BiTree T; scanf("%c",&ch); if(ch=='#')T=NULL; else{ T = (BiTree)malloc(sizeof(BiTNode)); T->data = ch; T->lchild = CreateBiTree(); T->rchild = CreateBiTree(); } return T;//返回根节点}//先序遍历void PreOrderTraverse(BiTree T){ if(T){ printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); }}//中序遍历void InOrderTraverse(BiTree T){ if(T){ InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild); }}//后序遍历void PostOrderTraverse(BiTree T){ if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); }}//求二叉树的深度int Depth(BiTree T) {int dep=0,depl,depr;if(!T) dep=0;else{depl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);}return dep;}//计算叶子节点数int leef(BiTree T){if(!T)return 0;elseif(T->lchild ==NULL&&T->rchild ==NULL)return 1;elsereturn leef(T->lchild) +leef(T->rchild );}//主函数void main(){ BiTree T;printf("请按先序输入序列（其中的“#”表示空）\n\n"); T = CreateBiTree();//建立二叉树printf("\n先序遍历结果为：");PreOrderTraverse(T);//先序遍历输出printf("\n\n中序遍历结果为：");InOrderTraverse(T);//中序遍历输出printf("\n\n后序遍历结果为：");PostOrderTraverse(T);//后序遍历输出printf("\n\n二叉树深度为：%d\n",Depth(T));Depth(T);//计算二叉树深printf("\n叶子节点数为：%d\n\n",leef(T));leef(T);//计算叶子节点数}
