上机实验报告
课程名称： 数据结构A 实验题目： 二叉树操作 专业班级： 计算机1501 学 号： 3150602020 姓名： 经普杰 完成日期： 2016.11.1 成 绩：
实验内容、目的和要求
（一） 实验内容
二叉树的建立和遍历。
（二） 实验目的
1. 进一步掌握指针变量的使用。
2. 掌握二叉树的结构特征以及各种存储结构的特点及使用范围。 3. 掌握用指针类型描述、访问和处理二叉树的运算。
4. 掌握栈或队列的使用。
（三） 实验要求
本实验要求实现以下功能：
1. 按前序次序建立一棵二叉树，以‘＃’表示空。 2. 中序、后序遍历该二叉树，输出遍历序列。
3. 求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。
4. 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅
助存储结构实现二叉树的层次遍历算法。
程序中使用的数据结构及符号说明
主要使用了
While循环语句 for循环语句 二叉树链表的建立 对二叉树的遍历 计算二叉树的高度 计算叶子节点的数量
程序的主要流程图
程序主要模块的功能说明
本程序分为四个类建立，分别为node类，linkqueue类，bintreenode类，bintreelink类 四个类中
node类:定义一个普通节点类,用于构建队列类
Linkqueue类：这是一个队列类，用于进行二叉链表的层次遍历，将二叉链表中的数据入队再出队以达到层次遍历的目的。
Bintreenode类：是建立一个二叉链表节点类，建立这样一个类，组成二叉链表。即二叉链表是由多个二叉链表类节点组合而成的。这个类中应包括，二叉树中的一个节点的全部内容，包括数据data，左子树leftchild，右子树rightchild，其中操作是对bintreenode进行初始化。 Bintreelink类：是整个程序的主要部分，这是一个二叉链表类，这个类由多个二叉链表类节点组成，这个链表即为二叉树的体现，在这个类中，包括对二叉树的操作。首先，定义数据成员：二叉树根节点。包括一系类对二叉链表的操作的函数成员：preorder（先序遍历）inorder（中序遍历），postorder（后续遍历），levelorder（层次遍历）height求二叉树的高度，leaf求二叉树叶子节点数。
程序运行时的初值和运行结果
【测试数据】
输入以下字符串，建立二叉树：ABC##DE#G##F### 输出中序遍历序列应为：CBEGDFA 输出后序遍历序列应为：CGEFDBA 输出二叉树的深度应为：5 输出二叉树的叶子数目应为：3
收获及体会
通过本次二叉树操作的实验，我基本了解了如何建立二叉树，二叉树的遍历操作，
求二叉树的高度，叶子节点数，将树上的一些伪代码算法实现为真正的c++算法，使我更加了解这些算法操作的含义。同时分清了二叉树链表节点类和二叉链表类之间的关系，明确对二叉链表的操作应该体现在二叉链表类中，二叉链表又是由二叉链表节点构成。了解了二叉链表的先序，中序，后序遍历在代码上的区别。
但是在这次实验中，发现自己对c++语言仍较为生疏，编写代码的方式不够程序，导致语言不规范，带来了许多不必要的麻烦，例如在建立二叉树的函数中，有一段代码为 If（ch==“#”）r=NULL；在开始的时候我错误的写成了If（ch=“#”）r=NULL；导致程序不能正常输入，只输入一个数据，程序就自动跳出循环，我在这个问题上多次检查，即使发现了问题出现在建立二叉树时，对代码多次检查都没有发现这个细小的错误，导致浪费了大量时间。
同时发现自己对二叉树的建立也不是很清楚，不知该如何下手，是通过百度 csdn等途径得知，不过对于遍历方面理解尚可。
源程序 Bintreenode.h
#pragma once #include
char data;
bintreenode*leftchild; bintreenode*rightchild; bintreenode();
bintreenode(char d, bintreenode*lchild, ~bintreenode();
#pragma once #include
bintreenode*r; bintreelink(); ~bintreelink();
void creatbitree(bintreenode*&r); void preorder(bintreenode*r); void Inorder(bintreenode*r); void postorder(bintreenode*r); int height(bintreenode*r); int leaf(bintreenode*r); public:
#include \bintreenode::bintreenode() { }
bintreenode::bintreenode(char d,
leftchild = rightchild = NULL;
bintreenode*lchild, bintreenode*rchild) {
data = d;
leftchild = lchild; rightchild = rchild;
}
Bintreelink.h
public:
bintreenode*rchild);
Bintreenode.cpp
void levelorder(bintreenode*r); };
Bintreelink.cpp
#include \
bintreelink::bintreelink() { r = NULL;
}
bintreelink::~bintreelink() { } void
bintreelink::creatbitree(bintreenode*&r) { char ch;
cout<<\请输入数据\ cin >> ch; if (ch == '#') r = NULL; else { r =new bintreenode; r->data = ch;
creatbitree(r->leftchild);
creatbitree(r->rightchild); }
}
void bintreelink::preorder(bintreenode*r) { if (r != NULL) { cout << r->data << \ preorder(r->leftchild); preorder(r->rightchild); }
}
void bintreelink::Inorder(bintreenode*r)//中序遍历 {
if (r != NULL) { Inorder(r->leftchild); cout << r->data << \ Inorder(r->rightchild);
}
}
void bintreelink::postorder(bintreenode*r)//后序遍历 { if (r != NULL) { postorder(r->leftchild); postorder(r->rightchild); cout << r->data << \
}
}
int bintreelink::height(bintreenode*r) //求二叉树的高度 { int lh = 0, rh = 0; if (r == NULL) return 0; else
{ lh = 1 + height(r->leftchild); rh = 1 + height(r->rightchild); }
return lh > rh ? lh : rh;
}
int bintreelink::leaf(bintreenode*r) //求二叉树的叶子节点数 {
// int count = 1; if (r == NULL) return 0; else
{ if ((r->leftchild == NULL)&&(r->rightchild==NULL))
return 1; else
{
int left, right;