实验报告
课程：数据结构与算法实验日期：-* 实验名称：二叉树的建立 一、实验目的
能够掌握二叉树
二、实验内容
必做部分
（1）上机任务：二叉树的创建（.cpp） 1.1）先给出二叉链表的类型定义
1.2）给出先序创建二叉树的算法函数定义
算法6.4：按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T（使用书上的输入序列建立该二叉树）： BiTreeCreateBiTree(BiTree &T)
1.3）给出打印二叉树内容的函数（打印方式自定义）
1.4）在主函数中增加调用入口，测试上述操作函数是否正常工作 （2）回答下述问题：
2.1）请问要创建如下二叉树，应输入怎样的字符序列？ 答：
2.2）怎样实现打印二叉树中的结点信息？是否能从算法6.4中得到什么启发？ 答：
2.3）假设一棵二叉树有100个结点，其中有29个度为1的结点，请问有多少个叶子结点？ 答：
2.4）一个有n个结点的二叉链表中有多少个空指针域？ 答：
选做部分
1、实现先序、中序、后序递归遍历二叉树的操作函数 2、编写统计一棵二叉树的叶子数的操作函数
3、在主函数中对1、2中操作进行调用，测试其是否正常工作
三、实验步骤
（1）上机任务：二叉树的创建（.cpp）
1.1）先给出二叉链表的类型定义
1.2）给出先序创建二叉树的算法函数定义
算法6.4：按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T（使用书上的输入序列建立该二叉树）： BiTreeCreateBiTree(BiTree &T)
1.3）给出打印二叉树内容的函数（打印方式自定义）
ABCFEGD
1.4）在主函数中增加调用入口，测试上述操作函数是否正常工作
（2）回答下述问题：
2.1）请问要创建如下二叉树，应输入怎样的字符序列？ 答：ABC???DEF??G???
2.2）怎样实现打印二叉树中的结点信息？是否能从算法6.4中得到什么启发？
答：递归打印二叉树，算法6.4是先序递归遍历二叉树，将算法做适当修改便可打印
2.3）假设一棵二叉树有100个结点，其中有29个度为1的结点，请问有多少个叶子结点？ 答：n0=n2+1;
n0+n2=100-29; n2=35 n0=36 有36个叶子结点
2.4）一个有n个结点的二叉链表中有多少个空指针域？ 答：n+1个 选做部分
1、 实现先序、中序、后序递归遍历二叉树的操作函数
编写统计一棵二叉树的叶子数的操作函数
2、 在主函数中对1、2中操作进行调用，测试其是否正常工作
数据结构与算法实验二叉树的建立
