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

1、 实验四 二叉树的基本操作一、实验目的：    （1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；   （2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想；   （3）掌握二叉树和叶子数、深度之间的关系及联系。二、实验内容：    构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。三、实验步骤：    (一) 需求分析     1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树

2、的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。    2程序的执行命令为：     1）构造结点类型，然后创建二叉树。    2）根据提示，从键盘输入各个结点。     3）通过选择一种方式（先序、中序或者后序）遍历。    4）输出结果，结束。  &

3、#160; (二)概要设计     1.二叉树的二叉链表结点存储类型定义       typedef struct Node         DataType data;        struct Node *LChild;        struct Node *RChild;       BitNode,*BitTree; 

4、;       2.建立如下图所示二叉树：            3.本程序包含六个模块        1) 主程序模块         2)先序遍历模块        3)中序遍历模块        4)后序遍历模块        5）叶子数模块    &#

5、160;   6）深度模块 四、测试结果       1. 进入演示程序后的显示主界面：      请输入二叉树中的元素；      先序、中序、后序遍历和叶子数、深度分别输出结果。      2.测试结果       以扩展先序遍历序列输入，其中#代表空子树：ABC#DE#G#F#        先序遍历序列为：ABCDEGF 

6、0;       中序遍历序列为：CBEGDFA         后序遍历序列为：CGEFDBA       此二叉树的叶子数为：3        此二叉树的深度为：5       3.程序运行结果截图：五、源代码#include#include/节点声明，数据域、左孩子指针、右孩子指针typedef struct BiTNode    char data; 

7、;   struct BiTNode *lchild,*rchild;BiTNode,*BiTree;              /先序建立二叉树BiTree CreateBiTree()    char ch;BiTree T;    scanf("%c",&ch);    if(ch='#')T=NULL;    else        T = (B

8、iTree)malloc(sizeof(BiTNode);        T->data = ch;        T->lchild = CreateBiTree();        T->rchild = CreateBiTree();        return T;/返回根节点/先序遍历void PreOrderTraverse(BiTree T)    if(T)   

9、    printf("%c",T->data);       PreOrderTraverse(T->lchild);       PreOrderTraverse(T->rchild);     /中序遍历void InOrderTraverse(BiTree T)    if(T)       InOrderTraverse(T->lchild); 

10、;      printf("%c",T->data);       InOrderTraverse(T->rchild);    /后序遍历void PostOrderTraverse(BiTree T)    if(T)       PostOrderTraverse(T->lchild);       PostOrderTraverse(T->rchild)

11、;       printf("%c",T->data);    /求二叉树的深度int Depth(BiTree T)   int dep=0,depl,depr;if(!T) dep=0;elsedepl=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->l

12、child =NULL&&T->rchild =NULL)return 1;else return leef(T->lchild) +leef(T->rchild );/主函数void main()    BiTree T;printf("请按先序输入序列（其中的“#”表示空）nn");    T = CreateBiTree();/建立二叉树printf("n先序遍历结果为：");PreOrderTraverse(T);/先序遍历输出printf("nn中序遍历结果为：");InOrderT