《数据结构》课程二叉树的操作实验指导
一、实验名称和性质
二、实验目的
1．理解二叉树的类型定义与性质。
2．掌握二叉树的二叉链表存储结构的表示和实现方法。
3．掌握二叉树遍历操作的算法实现。
4．熟悉二叉树遍历操作的应用。
三、实验内容
1．建立二叉树的二叉链表存储结构。
2．实现二叉树的先序、中序和后序三种遍历操作（验证性内容）。
3．应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作（设计性内容）。
4．求从二叉树根结点到指定结点p之间的路径（应用性设计内容）。
四、实验的软硬件环境要求
硬件环境要求：
PC机（单机）
使用的软件名称、版本号以及模块：
Windows环境下的TurboC2.0以上或VC++
五、知识准备
前期要求掌握二叉树的二叉链表的存储结构表示和三种遍历操作算法。
六、验证性实验
1．实验要求
编程实现如下功能：
（1）假设二叉树的结点值是字符，根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。
（2）对二叉树进行先序、中序和后序遍历操作，并输出遍历序列，观察输出的序列是否与逻辑上的序列一致。
（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种遍历操作。
2. 实验相关原理：
二叉树的形式定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。
二叉树定义二叉树的二叉链表存储结构描述为：
typedef char Telemtype;
typedef  struct  Bitnode
{  Telemtype  data;/*数据域*/
struct  Bitnode *lchild, *rchild;
/*指针域，分别指向该结点的左、右孩子*/
}Bitnode,*Bitree;
【核心算法提示】
二叉树的遍历是指按某条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。其中先序、中序和后序遍历操作步骤分别为：
（1）先序遍历：若二叉树为空树，则空操作；否则先访问根结点，再先序遍历左子树，最后先序遍历右子树。
（2）先序遍历：若二叉树为空树，则空操作；否则先中序遍历左子树，再访问根结点，最后中序遍历
右子树。
（3）先序遍历：若二叉树为空树，则空操作；否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。
注意：这里的“访问”的含义可以很广，几乎可以含盖对结点的任何一种操作。如：输出结点的信息、判断结点是否为叶子结点等等。
由于二叉树是一种递归定义，所以，要根据二叉树的某种遍历序列来实现建立一棵二叉树的二叉链表存储结构，则可以模仿对二叉树遍历的方法来加以实现。如：如果输入的是一棵二叉树的完整先序遍历序列，则可利用先序遍历方法先生成根结点，再用递归函数调用来实现左子树和右子树的建立。所谓完整的先序遍历序列就是在先序遍历序列中加入空树信息。【核心算法描述】
void createbitree(Bitree  &T)
/*根据输入的完整先序遍历序列建立一棵二叉树*/
{  scanf("%c",&x);  /*读取完整先序序列中的一个字符*/
if(x==‘#’)  T=NULL;
else
{ T=(Bitree)malloc(sizeof(Bitnode));/*生成根结点*/
T->data=x;
createbitree(T->lchild);/*递归建立左子树*/
createbitree(T->rchild); /*递归建立右子树*/
}
}
void  preorder(Bitree  T) /*先序遍历二叉树*/
{ if(T!=NULL)/*若二叉树非空*/
{ visit(T->data); /*访问根结点*/
preorder(T->lchild); /*递归先序遍历左子树*/
preorder(T->rchild); /*递归先序遍历右子树*/
}
}
void  inorder(Bitree  T) /*中序遍历二叉树*/
{ if(T!=NULL) /*若二叉树非空*/
{ inorder(T->lchild); /*递归中序遍历左子树*/
visit(T->data); /*访问根结点*/
inorder(T->rchild); /*递归中序遍历右子树*/ }
}
void  postorder(Bitree  T) /*后序遍历二叉树*/
{ if(T!=NULL) /*若二叉树非空*/
{ postorder(T->lchild); /*递归后序遍历左子树*/          postorder(T->rchild); /*递归后序遍历右子树*/            visit(T->data); /*访问根结点*/
}
}
3．源程序代码参考
#include <stdio.h>
typedef struct Bitnode
{char data;
struct Bitnode *lchild,*rchild;
}Bitnode,*Bitree;
Bitree creat(Bitree T)/*建立二叉树函数*/
{ char x;
scanf("%c",&x);
if (x=='#') T=NULL;
else
{T=(Bitree)malloc(sizeof(Bitnode));
if (!T)
{printf("OVERFLOW\n");
exit(-1);
}
else
{T->data=x;
T->lchild=creat(T->lchild);
T->rchild=creat(T->rchild);
}
}
return T;
}
Bitree preorder(Bitree T)/*先序遍历二叉树函数*/
{ if (T!=NULL)
{ printf("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void midorder(Bitree T) /*中序遍历二叉树函数*/
{ if (T!=NULL)
{ midorder(T->lchild);
printf("%c",T->data);
midorder(T->rchild);
}
}
void backorder(Bitree T) /*后序遍历二叉树函数*/
{ if (T!=NULL)
{ backorder(T->lchild);
backorder(T->rchild);
printf("%c",T->data);
}
}
main()/*主函数*/
{ Bitree T=NULL; char x;
printf("creat tree!\n");/*请求输入二叉树中各个元素*/
T=creat(T);/*调用建立二叉树函数*/
while(1)
{ printf("  1-preorder\n");
printf("  2-midorder\n");
printf("  3-backorder\n");
printf("  4-exit\n");
printf("please input the choose!(1-4):");/*请求选择遍历方式*/        scanf("%d",&x);
switch(x)
{case 1: printf("the preorder is:");
preorder(T); /*调用先序遍历二叉树函数*/
break;
case 2: printf("the midorder is:");
midorder(T); /*调用中序遍历二叉树函数*/
break;
case 3: printf("the backorder is:");
backorder(T); /*调用后序遍历二叉树函数*/
break;
case 4: return;
default:printf("ERROR!\n");
}
printf("\n");
}
}
4．运行结果参考如图5-1所示：
图5-1： 验证性实验运行结果
说明：上述对应的二叉树如图5-2所示。
七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成)
1．编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树，并判断这两棵二叉树是否相等。
⑴ 实验要求
① 假设二叉树的结点值是字符，请分别根据输入的两棵二叉树的先序遍历序列和中序遍历序列来建立二叉链表表示的两棵二叉树。 a  b  c  d e  f  图5-2：建立的二叉树

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。