实验报告四

姓名：陈聪

学号：142208100149 一、实验目的

1、、掌握二叉树的定义、性质及储存方式，各种遍历算法

2、采用二叉树链表作为存储结构，完成二叉树的建立，先序，中序，后序及按参差遍历的操作，求所有叶子及结点总数

3、调试程序，设计一颗二叉树，输入完全二叉树的先序序列，用#代表虚节点（空指针），如：ABD###CE##F##

二、算法思想

1、先根遍历二叉树

若二叉树为空则执行空操作，否则一次执行以下三个操作 ①先访问根节点 ②先根遍历左子树 ③先根遍历右子树

2、中根遍历、后根遍历（同理）

三、程序数据结构的定义

1、创建个二叉树

BinTree CreatBinTree(void)

2、先根遍历

void Preorder(BinTree T)

3、中根遍历 void Inorder(BinTree T) 4、后跟遍历

void Postorder(BinTree T 5、层次遍历

int PrintNodeAtLevel(BinTree T, int level) void TranverseTree(BinTree T

6、叶子节点数 int leafcount(BinTree T) 注：程序结构截图

四、程序代码截图

①头文件，定义部分

②创建二叉树

③先根遍历

④中根遍历

⑤后根遍历

⑥层次遍历

⑦叶子节点数

⑧主函数

五、程序操作说明

①开始输入二叉树，以#结尾，例如AB##C##

②程序自动输出先根、中根、后根、层次遍历、叶子节点数等

注意：

① 程序在visual studio 2013环境中编写的，有可能存在不兼容或者打不开的问题

② 输入二叉树的时候一定需要是完全二叉树，没有的地方用# 代替