data<<\" \"; if (temp->lchild) { q.push(temp->lchild); }if(temp->rchild) { q.push(temp->rchild); } } } }
//先序遍历
void preOrder(BiTree t) { if (t == NULL) { return; }
cout << t->data<<\" \"; preOrder(t->lchild); preOrder(t->rchild); }
//中序遍历
void inOrder(BiTree t) { if (t == NULL) { return; }
inOrder(t->lchild); cout << t->data<<\" \"; inOrder(t->rchild); }
//后序遍历
void postOrder(BiTree t) { if (t == NULL) { return; }
postOrder(t->lchild); postOrder(t->rchild); cout << t->data << \" \"; }
Main.cpp：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.
#include \"BiTNode.h\"
int main(){ BiTree t=NULL;
cout << \"***************采用递归函数构造一个二叉树 cout << \"请输入二叉树的字符序列：\"; if (t = createBiTree(t)) {
cout << \"二叉树创建成功！\" << endl; cout << \"先序遍历：\" << endl; preOrder(t);
cout << \"\\n中序遍历：\" << endl; inOrder(t);
cout << \"\\n后序遍历：\" << endl; postOrder(t);
cout << \"\\n层序遍历：\" << endl; levelOrder(t); } else {
cout << \"很遗憾创建二叉树失败！\" << endl; }
return 0; }
********************\" << endl;
3) 叶子结点统计的算法
创建二叉树的算法在前面实验中已经写过，这里只写计算叶子结点数的算法： 在BiTNode.h中添加以下内容：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
//计算叶子节点 int leafNumber = 0;
void getLeafNumber(BiTree t) { if (t) {
if (t->lchild == NULL && t->rchild == NULL) { leafNumber++;
cout<<\"叶子节数据：\" << t->data << endl; }
getLeafNumber(t->lchild); getLeafNumber(t->rchild); } }
Main.cpp：
1.
#include \"BiTNode.h\"
2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
int main() {
BiTree t = NULL;
cout << \"***************采用递归函数构造一个二叉树 cout << \"请输入二叉树的字符序列：\"; if (t = createBiTree(t)) {
cout << \"二叉树创建成功！\" << endl; getLeafNumber(t);
cout << \"这棵二叉树的叶子节点有\" << leafNumber << \"个。 } else {
cout << \"很遗憾创建二叉树失败！\" << endl; }
return 0; }
********************\" << endl;
\" << endl;
4) 二叉树深度统计算法
同理，这里只写统计深度的算法和main.cpp中的内容：
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
//二叉树深度统计
int getMaxLevel(BiTree t) { int dep1=0, dep2=0; if (t) {
dep1 = getMaxLevel(t->lchild); dep2 = getMaxLevel(t->rchild);
return dep1 > dep2 ? dep1 + 1 : dep2 + 1; } else { return 0; } }
Main.cpp：
1. 2. 3. 4. 5. 6. 7. 8.
#include \"BiTNode.h\" int main() {
BiTree t = NULL;
cout << \"***************采用递归函数构造一个二叉树 cout << \"请输入二叉树的字符序列：\"; if (t = createBiTree(t)) {
cout << \"二叉树创建成功！\" << endl;
cout <<\"这棵二叉树的深度是:\"<< getMaxLevel(t) << endl;
********************\" << endl;
9. 10. 11. 12. 13. 14.
} else {
cout << \"很遗憾创建二叉树失败！\" << endl; }
return 0; }
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行
结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
1) 二叉树创建的算法
测试如下二叉树：
图1-1
实验结果：
2) 二叉树各种遍历算法
测试二叉树如下：
图2-1
建立二叉树时应该对应输入：a b d h # # i # # e # j # # c f # k # # g # # 运行结果：
3) 叶子结点统计的算法
测试图2-1中的二叉树，结果为：
4) 二叉树深度统计算法
仍然测试图2-1的二叉树：
5．讨论（通过实验的一些体会、学会的知识和技能等）
1) 二叉树创建的算法
关于二叉树的创建，首先为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如“#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。上面的实验用了先序遍历来创建而二叉树，就首先要写出扩展二叉树的先序遍历序列，然后从键盘上输入序列就可以创建二叉树了。
在层序遍历二叉树的时候用到了队列的知识，在c++头文件queue中封装了队列，直接引入头文件就可以来使用队列，通过Queue<>就可以创建对象，利用队列的性质，实现层序遍历二叉树。 2) 二叉树各种遍历算法
二叉树的遍历主要分为四种：前序遍历，中序遍历，后序遍历以及层序遍历。下面简述一下上面程序主要运用的思想：前序遍历：若树为空，则空操作返回。否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树。中序遍历：若树为空，则空操作返回。否则，从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树。后序遍历：若树为空，则空操作返回。否则，从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。层序遍历：若树为空，则空操作返回。否则，从树的第一层，也就是根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序结点逐个访问。 3) 叶子结点统计的算法
统计叶子节点的算法设计与二叉树的几种遍历方法是分不开的，在本次实验中，采用先序遍历统计二叉树的叶子数，由于如果一个节点是叶子的话，其左右孩子均为空，所以可用左右孩子均为空的方法来判断是否为叶子节点，然后定义全局变量统计叶子节点即可。
4) 二叉树深度统计算法
求二叉树的深度算法实际上是递归的应用，运用递归找到二叉树的叶子各个叶子节点，并加以比较，找到最“深”的那个叶子节点，即为二叉树的深度。
