淮海工学院大数据结构第3次实验-树型大数据结构

实用文档

树结构算法实现与应用报告要求

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

E

D

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)); }