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