（7）将当前对头出栈，len++，打印出队元素
（8）如果出队元素的左子树的根节点不为空则入队,len--.
（9）如果出队元素的右子树的根节点不为空则入队,len--.
4、
（1）利用指针temp指向根节点，并初始化一个队列。
（2）将temp指向的当点节点入队。并声明当前层最大节点数为0
（3）重复指向以下所有步骤，直到遇到break语句。若遇到break语句则结束整个程序并返回最大节点数。
}
if(top <= 0)return;
top--;
p = Stack[top];
printf("%c",p->data);
p = p->rchild;
}
}
intmain()
{
BitNode *root;
root = CreateTree();
printf("前序遍历结果");
PreOrder(root);
2、在前序遍历的过程中利用中间变量交换左右子树。
3、利用队列。当上一层中的数据全部出队（遍历）完毕再遍历本层节点。
4、高度：获取所有节点到根节点的最长路径。宽度：在层次遍历的基础上，返回最多节点的层的节点数。
算法描述：可以用自然语言、伪代码或流程图等方式
1、创建树：
（1）声明节点
（2）输入当前节点，若输入为#则当前节点为空，否则为当前节点申请空间。
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
BitTree *Exchange(BitTree *T)
{
BitTree *temp;
if(T == NULL)returnNULL;
temp = T->lchild;
T->lchild = T->rchild;
（4）用变量len记录队列中二叉树当前层的节点数。
（5）若len为0则结束整个程序，否则执行第六步。
（6）当len>0（即队列中还有前层的节点时）重复七~九步。否则执行第十步。
（7）将当前对头出栈，len++，打印出队元素
（8）如果出队元素的左子树的根节点不为空则入队,len--.
（9）如果出队元素的右子树的根节点不为空则入队,len--.
（2）后序遍历当前节点的左子树。
（3）后序遍历当前节点的右子树。
（3）打印当前节点的data。
2、
（1）若当前节点为空则返回NULL,结束。否则执行下一步。
（2）利用中间变量temp交换当前节点的左右子树。
（3）交换当前的点左子树根节点的左右子树。
（4）交换当前节点右子树根节点的左右子树。
（4）返回根节点。
二、实验题目与要求
1.每位同学按下述要求实现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法
1）问题描述：在主程序中提供下列菜单：
1…建立树
2…前序遍历树
3…中序(非递归)遍历树
4…后序遍历树0…结束
2）实验要求：
①定义下列过程：
CreateTree():按从键盘输入的前序序列，创建树
PreOrderTree()：前序遍历树（递归）
InOrderTree()：中序(非递归)遍历树
LaOrderTree():后序遍历树（递归）
②每位同学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。
3）注意问题:
①注意理解递归算法的执行步骤。
②注意字符类型数据在输入时的处理。
③重点理解如何利用栈结构实现非递归算
2.编写算法交换二叉树中所有结点的左、右子树
T->lchild = CreateTree();
T->rchild = CreateTree();
}
returnT;
}
voidPreOrder(BitNode *T)
{
if(T == NULL)return;
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
3、
（1）利用指针temp指向根节点，并初始化一个队列。
（2）将temp指向的当点节点入队。
（3）重复指向以下所有步骤，直到遇到break语句。
（4）用变量len记录队列中二叉树当前层的节点数。
（5）若len为0则结束整个程序，否则执行第六步。
（6）当len>0（即队列中还有前层的节点时）重复指向以下所有步骤。否则执行第三步。
printf("\n");
printf("中序遍历结果");
InOrder(root);
printf("\n");
printf("后序遍历结果");
PostOrder(root);
printf("\n");
return0;
}
2、
#include<stdio.h>
#include<stdlib.h>
typedefcharElemtype;
1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树
2）实验要求：以二叉链表作为存储结构
3.试编写按层次顺序遍历二叉树的算法
1）问题描述：编写按层次顺序遍历二叉树的算法
2）实验要求：以二叉链表作为存储结构
4.编写算法求二叉树高度及宽度。
1）问题描述：二叉树高度是指树中所有节点的最大层数，二叉树宽度是指在二叉树的各层上，具有节点数最多的那一层上的节点总数。
输出：
4、
输入：ABH##FD###E#CK##G##
输出：
算法时间复杂度分析
1、O(n).
2、O(n).
3、O(n).
4、O(n).
四、收获与体会
学了二叉树之后顿时感觉之前的内容有多简单了。二叉树中用到很多递归算法，看起来很难懂。需要一步一步的跟下去才能理解，但是理解还远远不够，关键是是自己能写出来属于自己的递归算法。经过长时间的练习，我已经能写出来一些简单的递归算法了，但是稍微难一点的就写不出来了。后面的图还更难。革命尚未成功，诸君还需努力呐。我相信经过自己不屑的练习，我会提高的！
printf("\n中序遍历交换后的二叉树：");
InOrder(root);
printf("\n");
return0;
}
3、
#include<stdio.h>
#include<stdlib.h>
#defineMaxSize 100
typedefcharElemtype;
typedefstructBitTree
}
voidPostOrder(BitNode *T)
{
if(T == NULL)return;
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
voidInOrder(BitNode *T)
{
BitNode *p,*q;
BitNode *Stack[MaxSize];
（3）将输入的值赋给当前节点的data域，并前序建立当前节点的左子树和右子树。
（4）返回当前节点。
前序遍历树：
（1）若当前节点为空则返回上一级函数，否则打印当前节点。
（2）前序遍历当前节点的左子树。
（3）前序遍历当前节点的右子树。
中序遍历树：
（1）声明一个顺序栈，并用p指针指向当前节点。
（2）若当前节点和栈不同时为空则重复进行下一步。否则程序结束
{
Elemtype data;
structBitTree *lchild;
structBitTree *rchild;
}BitTree;
typedefBitTree Elementtype;
typedefstructQueueNode
{
Elementtype *base;
intfront;
intrear;
实验报告
学院（系）名称：计算机与通信工程学院
姓名
* *
学号
********
专业
计算机科学与技术
班级
2015级*班
实验项目
实验三：二叉树操作
课程名称
数据结构与算法
课程代码
0661013
实验时间
年月日第节
实验地点
7-***
考核标准
实验过程
25分
程序运行
20分
回答问题
15分
实验报告
30分
特色
功能
5分
考勤违纪情况
inttop = 0;
p = T;
while(!(p == NULL && top == 0))
{
while(p != NULL)
{
if(top < MaxSize-1)
{
Stack[top] = p;
top++;
}else{
printf("栈溢出");
exit(0);
}
p = p->lchild;
（10）当前层最大节点数等于上一层最大节点数和当前队列中的节点数中较大的一个。
执行第三步。
算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等