数据结构-实验四-二叉树的基本操作

1、 实验四 二叉树的基本操作一、实验目的： （1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； （2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想； （3）掌握二叉树和叶子数、深度之间的关系及联系。二、实验内容： 构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。三、实验步骤： (一) 需求分析 1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法

2、，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。 2程序的执行命令为： 1）构造结点类型，然后创建二叉树。 2）根据提示，从键盘输入各个结点。 3）通过选择一种方式（先序、中序或者后序）遍历。 4）输出结果，结束。 (二)概要设计 1.二叉树的二叉链表结点存储类型定义 typedef struct Node DataType data; struct Node *LChild; struct Node *RChild; BitNode,*BitTree; 2.建立如下图所示二叉树： 3.本程序包含六个模块 1) 主程序模块 2)先序遍历模块 3)中序遍

3、历模块 4)后序遍历模块 5）叶子数模块 6）深度模块四、测试结果 1. 进入演示程序后的显示主界面： 请输入二叉树中的元素； 先序、中序、后序遍历和叶子数、深度分别输出结果。 2.测试结果 以扩展先序遍历序列输入，其中#代表空子树：ABC#DE#G#F# 先序遍历序列为：ABCDEGF 中序遍历序列为：CBEGDFA 后序遍历序列为：CGEFDBA 此二叉树的叶子数为：3 此二叉树的深度为：5 3.程序运行结果截图：五、源代码#include#include/节点声明，数据域、左孩子指针、右孩子指针typedef struct BiTNode char data; struct BiTNod

4、e *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); P

5、reOrderTraverse(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); /求二叉树的深度i

6、nt Depth(BiTree T) int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild);depr=Depth(T-rchild);dep=1+(depldepr?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(请按先序输入序列（其中的“#”表示空）nn); T = CreateBiTree();/建立二叉树printf(n先序遍历结果为：);PreOrderTraverse(T);/先序遍历输出printf(nn中序遍历结果为：);InOrderTraverse(T);/中序遍历输出printf(nn后序遍历结果为：);PostOrderTrave