### 数据结构实验报告：二叉树
#### 一、实验目的和要求
1. **实验目的**：
- 熟悉并掌握二叉树的基本结构及其特征。
- 了解与二叉树相关的证明方法。
- 理解二叉树的存储结构，并知道其适用范围。
2. **实验要求**：
- 掌握二叉树的各种遍历策略（包括前序、中序、后序）的递归和非递归算法。
- 能够灵活运用这些遍历算法来实现对二叉树的操作，例如查找、插入、删除等。
#### 二、实验环境
- **操作系统**：Windows 98/2000/XP
- **开发工具**：Visual C++ 6.0
- **编程语言**：C/C++
#### 三、程序逻辑框图
[此处省略图片]
#### 四、程序源代码解析
##### 1. 数据结构定义
- **二叉树节点** (`BiTNode`)：用于表示二叉树中的一个节点，包含节点值、左子树指针和右子树指针。
- **栈结构** (`SqStack`)：用于实现非递归遍历过程中所需的辅助栈，包括栈底、栈顶和栈大小等字段。
```c
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef struct {
SElemType *base, *top;
int stacksize;
} SqStack;
```
##### 2. 栈的基本操作
- **初始化栈** (`InitStack`)：分配内存空间，设置栈顶和栈大小。
- **获取栈顶元素** (`GetTop`)：返回栈顶元素。
- **入栈** (`Push`)：将元素加入栈顶。
- **出栈** (`Pop`)：移除栈顶元素并返回。
- **判断栈是否为空** (`StackEmpty`)：检查栈是否为空。
```c
Status InitStack(SqStack &S) {
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base) return ERROR;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
// 其他栈操作...
```
##### 3. 二叉树操作
- **创建二叉树** (`CreateBiTree`)：根据输入字符序列构建二叉树。
- **递归遍历** (`PreOrderTraverse`)：采用递归方式实现前序遍历。
- **非递归遍历（中序）** (`InOrderTraverse`)：使用栈实现非递归中序遍历。
- **求二叉树高度** (`HeightOfBiTree`)：递归计算二叉树的高度。
```c
void CreateBiTree(BiTree &t) {
int ch = getchar();
if (ch == '') t = NULL;
else {
if (!(t = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
t->data = ch;
CreateBiTree(t->lchild);
CreateBiTree(t->rchild);
}
}
void PreOrderTraverse(BiTTree t) {
if (t) {
printf("%c", t->data);
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
}
void InOrderTraverse(BiTTree t) {
SqStack s;
BiTree p;
InitStack(s);
Push(s, t);
while (!StackEmpty(s)) {
while (GetTop(s, p) && p) {
Push(s, p->lchild);
}
Pop(s, p);
if (!StackEmpty(s)) {
Pop(s, p);
printf("%c", p->data);
Push(s, p->rchild);
}
}
}
int HeightOfBiTree(BiTTree t) {
if (t == NULL) return 0;
if (t->lchild == NULL && t->rchild == NULL) return 1;
else {
return 1 + max(HeightOfBiTree(t->lchild), HeightOfBiTree(t->rchild));
}
}
```
#### 五、实验总结
通过本次实验，我们深入了解了二叉树的基本概念以及其实现细节。特别是对于二叉树的遍历算法有了更深刻的理解。掌握了二叉树的递归和非递归遍历算法，能够灵活应用这些算法解决实际问题。此外，还学习了如何使用栈来辅助实现非递归遍历，这对于理解数据结构中的高级概念非常有帮助。在实际编码过程中，我们也遇到了一些挑战，比如如何有效地管理内存、如何正确处理递归调用等，但通过不断地调试和优化，最终成功完成了实验任务。这次实验不仅加深了我们对二叉树这一基础数据结构的认识，也为后续学习更复杂的数据结构和算法奠定了坚实的基础。
