哈尔滨工业大学计算机科学与技术学院
实验报告
课程名称：数据结构与算法
科学与技术四班
1110310422
课程类型：必修 实验项目名称：树型结构的建立与遍历 实验题目： 二叉树的运用 班级：计算机 学号： 姓名：胡明
一、实验目的 （1）通过本实验，掌握建立二叉链表的方法，以便在适当的时候选择适当的建立方式；
（2）通过本实验，理解二叉树这种基本数据结构，并掌握遍历二叉树的先序、中序、 后序递归遍历算法，并在深入理解递归算法的基础上实现非递归算法；
（3）通过本实验，理解广义表并实现广义表对二叉树顺序存储并打印；
二、实验要求及实验环境
1、实验要求：
(1) 至少用两种方法，编写建立二叉树的二叉链表存储结构的程序，并用广义表的形式显示并保存二叉树；
(2) 采用二叉树的二叉链表存储结构，编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法，并显示二叉树和相应的遍历序列；
(3) 在二叉树的二叉链表存储结构基础上，编写程序实现二叉树的先序、中序和后序线索链表存储结构建立的算法，并用广义表的形式显示和保存二叉树的线索链表；
(4) 在二叉树的线索链表存储结构上，编写程序分别实现求一个结点的先序（中序、后序）的后继结点的算法；
(5) 在 (4) 基础上，编写程序实现对线索二叉树进行先序、中序和后序遍历的非递归算法，并显示线索二叉树和相应的遍历序列。
2、实验环境：带有Codeblocks 的电脑
三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）
1、逻辑设计
（1）层次建立算法：
1.输入节点i 和数据m 不是0和#循环
1.1申请节点q, 把节点赋给q 的数据域；
1.2将其左右子链置成空;
1.3.1如果i=0，P 为根节点
1.3.2否则父节点的编号j 为i/2;
1.3.2.1如果i 为奇数，为j 右儿子
1.3.2.1如果i 为偶数，为j 左儿子
（2）先序递归建立
1.输入节点的字符
1.1如果字符为#,T为空；
1.2否则申请节点T ；
1.2.1将字符赋给T 的数据域；
1.2.2递归的建立左子树；
1.2.3递归的建立右子树；
（3）先序递归遍历
1.如果树T 不为空
1.1输出T 的数据域
1.2递归的遍历左子树
1.3递归的遍历右子树
（4）中序递归遍历
1.如果树T 不为空
1.1递归的遍历左子树
1.2输出T 的数据域
1.3递归的遍历右子树
（5）后序递归遍历
1.如果树T 不为空
1.1递归的遍历左子树
1.3输出T 的数据域
（6）先序遍历非递归算法
1.栈s 初始化；
2.
循
环
直
到
r
o
o
t
为
空
且
栈
s
为
空
2
.
1
当
r
o
o
t
不
空
时
循
环
2
.
1
.
1
出
r
o
o
t
-
>
d
a
t
a
;
2.1.2 将指针
root 的值保存到
栈中；
2.1.3
继续
遍历
root
的左
子树
2
.
2
如
果
栈
s
不
空
，
则
2.2.1 将
栈顶元素
弹出至
root ；
2.2.2 准备遍历root 的右子树；
（7）中序遍历非递归算法
1.栈s 初始化；
2.
循
环
直
到
r
o
o
t
为
空
且
栈
s
为
空
2
.
1
当
r
o
o
t
不
空
时
循
环
2.1.1 将指针root 的值保存到栈中；
2.1.2 继续遍历root
的左子树
2
.
2
如
果
栈
s
不
空，则
2.2.1 将栈顶元素弹出至root ； 2. 2. 2 输出r o o t -
>d a t a ;
2.2.3 准备遍历root 的右子树； （8）后序遍历非递归算法 1. 栈s 初始化； 2. 循环直到ro ot 为空且栈s
为空
2. 1 当r o o t 非空时循环
2.1.1 将root 连同标志flag=1 入栈； 2.1.2 继续
遍历root 的左子树；
2.2 当栈s 非空且栈顶元素的标志为2 时，出栈并输出栈顶结点;
2.3 若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树； （9） 层次遍历算法 1. 队列Q 初始化；
2. 如果二叉树非空，将根指针入队； 3. 循环直到队列Q 为空
3.1 q=队列Q 的队头元素出队； 3. 2 访问结点q 的数据域；
3.3 若结点q 存在左孩子，则将左孩子指针入队；
3.4 若结点q 存在右孩子，则将右孩子指针入队；
（10）用数组存储广义表递归算法： 1.数组的初始化，和标志的设置i=0； 2. 左括号进数组,i++； 3. 树T 的广义表存储 3.1如果T 不为空
3.1.1如果左右子树都不为空，则字符进数组,i++;
3.1.2.1否则字符进数组,i++; 3.1.2.2左括号进数组,i++; 3.1.2.3递归遍历左子树 3.1.2.4逗号进数组,i++; 3.1.2.5递归遍历右子树 3.1.2.6右括号进数组,i++; 4.右括号进数组,i++
5用‘\0’标记数组结束，i++; 2、物理设计
流程图（最左边为主函数，右边为4个子函数及其调用关系）：
下面为上图两种建立方式（先序，层次）和六种遍历（先，还有广义表存储和打印的截图：
四、测试结果 中后根递归和非递归遍历）
五、系统不足与经验体会
1、系统不足
（1）由于时间的关系，没有写线索二叉树及其各种遍历算法和求后继节点的算法；
（2）由于空指针总是比节点多一个，造成很大的空间
浪费； 2、经验体会
（1）非递归算法其实就是把递归算法用循环和其他数据结构（本实验中对应的队列和栈）模拟出来，比起非递归算法，递归算法更直观易懂，但是非递归有助于更深入理解该种数据结构；
（2）在写非递归算法调试的时候，出现栈陷入死循环，这时候如果设立一个栈的判断空的函数那么就很容易知道看出自己设计算法的问题；
（3）很多关于二叉树的算法都是基于遍历二叉树的算法的，比如删除二叉树的算法和求高度的算法；
（4）图中的DFS 类似于二叉树中的先序遍历算法，这也是为什么在写非递归算法上用栈先进后出这种数据结构实现的原因，他们的共同特点都是尽可能的走远；
（5）给定一个先序遍历系列并不能唯一的确定二叉树，比如两个不同方向的斜树；
六、附录：源代码（带注释）
#include #include #include #include #define maxlen 100 using namespace std; struct BTtree {
char data;
BTtree *lchild; BTtree *rchild; };
char genelist[100];//保存广义表 int i;
BTtree* pre_creat_bt()//先序建立二叉树 {
char ch; BTtree *T; cin >> ch;
if(ch=='#') T=NULL; else {
T=(BTtree*)malloc(sizeof(BTtree)); T->data=ch;
// printf("\n请输入%c结点的左子结点(如果没有那么输入#代表空):",T->data ); T->lchild=pre_creat_bt();
// printf("\n请输入%c结点的右子结点(如果没有那么输入#代表空):",T->data ); T->rchild=pre_creat_bt(); }
return T; }
BTtree * level_create()//层次建立二叉链表 {
BTtree* s[maxlen]; int j; char ch;
BTtree *T,*p;
while(cin >> i >> ch&&(i!=0||ch!='#')) {
p=(BTtree*)malloc(sizeof(BTtree)); p->data=ch;
p->lchild=NULL; p->rchild=NULL; s[i]=p;
if(i==1)T=p; else {
j=i/2;
if(i%2==0)s[j]->lchild=p;//节点为偶数，i 为j 的左儿子 else s[j]->rchild=p;//节点为偶数，i 为j 的左儿子 } }
return T;
}
void pre_order(BTtree *T)//递归先根遍历二叉树
{
if(T!=NULL)
{
cout data;
pre_order(T->lchild);
pre_order(T->rchild);
}
}
void in_order(BTtree *T)//递归中序遍历二叉树
{
if(T!=NULL)
{
in_order(T->lchild);
cout data;
in_order(T->rchild);
}
}
void post_order(BTtree *T)//递归后根遍历二叉树
{
if(T!=NULL)
{
post_order(T->lchild);
post_order(T->rchild);
cout data;
}
}
void npre_order(BTtree *T)//非递归先根遍历二叉树
{
BTtree* STACK[maxlen];
int top=maxlen;
while(T!=NULL||top!=maxlen)
{
while(T!=NULL)
{
cout data;
STACK[--top]=T;
T=T->lchild;
}
if(top!=maxlen)
{
T=STACK[top++];
T=T->rchild;
}
}
}
/*
当树非空那么循环，访问，左走
若S 不空，取栈顶右走
*/
void nin_order(BTtree *T)//非递归中序遍历二叉树
{
BTtree* STACK[maxlen];
int top=maxlen;
while(T!=NULL||top!=maxlen)
{
if(T!=NULL)
{
STACK[--top]=T;
T=T->lchild;
}
else
{
T=STACK[top++];
cout data ;
T=T->rchild;
}
}
}
/*
树不空，左走一步不访问
若栈不空，取出栈顶访问 再访问父亲，再右走
*/
void npost_order(BTtree *T)//非递归后根遍历二叉树
{
struct STACK
{
BTtree* tree;
int flag;
} S[maxlen];
int top=maxlen;
BTtree * temp;
temp=T;
while(temp!=NULL||top!=maxlen)
{
if(temp!=NULL)
{
S[--top].tree=temp;
S[top].flag=1;
temp=temp->lchild;
}
else
{
if(S[top].flag==2)
{
T=S[top++].tree;
cout data;
}
else
{
S[top].flag=2;
temp=S[top].tree->rchild;
}
}
}
}
void lev_order(BTtree* T)
{
BTtree* Q[maxlen],*q=NULL;
int front=0,rear=0;//建立一个空的队列
if(T==NULL)return;
Q[rear++]=T;//将根指针入队
while(front!=rear)
{
q=Q[front];
cout data;
if(q->lchild!=NULL)
{
Q[rear]=q->lchild;//左儿子不是空，将它入队列
rear++;
}
if(q->rchild!=NULL)
{
Q[rear]=q->rchild;//右边儿子不是空，将它入队列
rear++;
}
front++;//完成上面之后将队首元素就可以出队进行下一次循环操作
}
}
void order(BTtree * T)//遍历二叉链表
{
printf("********递归遍历二叉链表***********\n");
printf("\n先序递归遍历二叉链表:");
pre_order(T);
printf("\n中序递归遍历二叉链表:");
in_order(T);
printf("\n后序递归遍历二叉链表:");
post_order(T);
printf("\n********非递归遍历二叉链表***********\n");
printf("\n先序非递归遍历二叉链表:");
npre_order(T);
printf("\n中序非递归遍历二叉链表:");
nin_order(T);
printf("\n后序非递归遍历二叉链表:");
npost_order(T);
printf("\n**********层次遍历二叉链表***********:\n");
lev_order(T);
}
void print_tree(BTtree *T) /*按广义表方式打印*/
{
if(T!=NULL)
{
if(T->lchild==NULL&&T->rchild==NULL)
{
genelist[i]=T->data;
i++;
}
else
{
genelist[i]=T->data;
i++;
genelist[i]='(';
i++;
print_tree(T->lchild);
genelist[i]=',';
i++;
print_tree(T->rchild);
genelist[i]=')';
i++;
}
}
}
void print(BTtree *T)
{
BTtree *t=T;
i=0;
genelist[i]='(';
i++;
print_tree(t);
genelist[i]=')';
i++;
genelist[i]='\0';
}
int main()
{
BTtree *pre_t=NULL,*lev_t=NULL;
int N;
printf("********输入1先序建立二叉链表***********\n********输入2层次建立二叉链表
***********\n********输入0退出***********\n");
while(cin >> N)
{
switch(N)
{
case 1:
printf("********先序建立二叉链表***********\n输入根节点(如果没有那么输入#代表空):"); pre_t=pre_creat_bt();
order(pre_t);//遍历二叉链表
printf("\n********二叉树用广义表表示为********:\n");
print(pre_t);
for(i=0; genelist[i]!='\0'; i++) cout
printf("\n");
break;
case 2:
printf("********层次建立二叉链表***********\n输入节点次序和元素:");
lev_t=level_create();
order(lev_t);//遍历二叉链表*/
printf("\n********二叉树用广义表表示为********:\n");
print(lev_t);
for(i=0; genelist[i]!='\0'; i++)cout
printf("\n");
break;
case 0:
break ;
default :
break;
}
memset(genelist,' ',sizeof(genelist));
printf("********输入1先序建立二叉链表***********\n********输入2层次建立二叉链表
***********\n********输入0退出***********\n"); }
return 0;
}
/*1A 3C 4D 5E 6F 7G 8H 9I 10J 0#*/