淮海工学院计算机科学系实验报告书
课程名：《数据结构》
题目：树型数据结构试验
班级：
学号：
姓名：
树结构算法实现与应用报告要求
1目的与要求:
1）熟练掌握二叉树的二叉链表表示及前序创建算法与实现；
2）熟练掌握二叉树的前序、中序和后序递归遍历算法与实现；
3）掌握中序遍历线索二叉树的基本算法与实现
4）掌握中序遍历线索化二叉树的算法与实现；
5）按照实验题目要求独立完成实验内容（提交程序清单及相关实验数据与运行结果）；
6）认真书写实验报告,并按时提交（本次实验第9周周三以前提交，不得延误）。
2 实验内容或题目
实验内容:
1）按照先序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态输入。
2）在第1）步建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。
3) 在第1) 步建立好的二叉链表树上实施前序遍历的叶子结点输出及其个数统计。
4）在第1) 步建立好的二叉链表树上实施二叉树性质三的验证；
5）在第1）步建立好的二叉链表树上实施中序非递归遍历，并输出相应遍历序列(选做)
6）中序线索化第1）步所建立的二叉链表树(选做)。
7）中序遍历第6）步所建立的线索二叉树，并输出遍历结果(选做)
（注释：实验要求完成的任务（各个实验内容）应以菜单机制显示和运行来逐项完成，即整个实验题目写一个主程序完成所有实验内容，并以菜单机制实施交互运行，而不要一个实验内容写一个主程序）
A
B
C D
E F
G
3 实验步骤与源程序
#include
#include
#include
typedef struct Node
{
char data;
struct Node *LChild; struct Node *RChild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree *bt)
{
char ch;
ch = getchar();
if(ch=='.')
*bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild));
CreateBiTree(&((*bt)->RChild));
}
void Visit(char ch)
{
printf("%c ",ch);
}
void PreOrder(BiTree root)
{
if (root!=NULL)
{
Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
void InOrder(BiTree root)
{
if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
void PostOrder(BiTree root)
{
if(root!=NULL)
{
PostOrder(root ->LChild);
PostOrder(root ->RChild);
Visit(root ->data);
}
}
void Pre(BiTree root)
{
if (root!=NULL)
{
if(root->LChild==NULL&&root->RChild==NULL)
{
printf("%c ",root->data);
}
Pre(root ->LChild);
Pre(root ->RChild);
}
}
int LeafCount(BiTree &T)
{
int num1,num2,num3;
if(!T) return 0;
if(T->LChild==NULL && T->RChild==NULL) return 1;
num1=LeafCount(T->LChild);
num2=LeafCount(T->RChild);
num3=num1+num2;
return (num3);
}
void main()
{
int i;
BiTree T;
printf("创建先序遍历序列二插树");
CreateBiTree(&T);
star:printf("\n请选择您要进行的操作:\n");
printf("1,显示先序遍历序列\n");
printf("2，显示中序遍历序列\n");
printf("3，显示后序遍历序列为\n");
printf("4，显示前序叶子节点及其个数\n");
scanf("%d",&i);
switch (i)
{
case 1:
printf("先序遍历序列为:"); PreOrder(T);printf("\n");goto star;break;
case 2:
printf("中序遍历序列为:"); InOrder(T);printf("\n");goto star;break;
case 3:
printf("后序遍历序列为:"); PostOrder(T);printf("\n");goto star;break;
case 4:
