数据结构实验报告04.doc

《数据结构》实验报告 班级姓名:邹维韬 学号:2012302516 E-mail: 396881328@日期:11.15 ◎实验题目: 输入一棵二叉树，使用二叉链表结构存储二叉树，并用递归方法输出先序、中序、后序三种遍历结果。 ◎实验目的：熟练掌握二叉树结构，能用二叉链表建立存储二叉树，并且可以用先序、中序、后序遍历输出二叉树 ◎实验内容：用广义表输入一个二叉树，用二叉链表创建二叉树，并用先序、中序、后序遍历输出。 一、需求分析 1.本演示程序中，输入的二叉树是任意的不为空的二叉树，输入形式为广义表形式的二叉树，输出为该二叉树的先序、中序、后序遍历输出。 2.本程序可以实现给定广义表形式的二叉树的创建，以及实现该二叉树的先序、中序、后序遍历输出。 3.程序执行的命令包括： （1）输入广义表形式的二叉树（2）创建二叉树（3）先序递归遍历输出（4）中序递归遍历输出（5）后序递归遍历输出 4.测试数据：输入：（-（+（a,*(b,-(c,d))）,+(e,f)）） 先序递归遍历输出: -+a*b-cd+ef 中序递归遍历输出: a+b*c-d-e+f 后序递归遍历输出: abcd-*+ef+- 二 概要设计 为了实现上述操作，应以二叉链表为存储结构。 基本操作 node *create(char a[20]) 创建二叉链表 void preorder(node *bt) 先序递归遍历输出 void inorder(node *bt) 中序递归遍历输出 void postorder(node *bt) 后序递归遍历输出 void NRPreorder(node *bt) 本程序包括五个模块 主程序模块 二叉树建立模块 先序递归遍历输出模块 中序递归遍历输出模块 后序递归遍历输出模块 三 详细设计 ??实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；画出函数的调用关系。 元素类型，节点类型和指针类型 typedef struct node { char data; struct node *lc; struct node *rc; }node; node *s[maxsize]; int top=-1; node *p; node *bt; 每个模块分析 (1)主程序模块 int main() { node *bt; char b[20]; printf(请输入二叉树:\n); scanf(%s,b); bt=create(b); printf(该二叉树的先序递归遍历序列为: ); preorder(bt); printf(\n); printf(该二叉树的中序递归遍历序列为: ); inorder(bt); printf(\n); printf(该二叉树的后序递归遍历序列为: ); postorder(bt); printf(\n); getchar(); getchar(); return 0; } (2)二叉树建立模块 node *create(char a[20]) { node *p; int i=1; /*以广义表形式输入的二叉树第一个必为左括号*/ node *bt; top++; p=(node *)malloc(sizeof(node)); /*因是左括号，申请新节点*/ p-lc=NULL; /*左右孩子置空*/ p-rc=NULL; bt=p; /*使根节点指向新申请节点*/ s[top]=p; /*将指针入栈*/ while(a[i]!=\0) /*字符数组读到\0结束循环*/ { if(a[i]==() /*如果读到左括号*/ { if(a[i+1]!=,) /*如果左括号后边不是逗号，申请新节点，左右孩子置空，栈顶元素的左孩子指向新节点，指针入栈*/ { p=(node *)malloc(sizeof(node)); p-lc=NULL; p-rc=NULL; s[top]-lc=p; top++; s[top]=p; } else /*否则栈顶元素左孩子为空，为保持入栈出栈平衡，栈顶加