算法与数据结构实验册(顾原翔1413101019)(1)(1)

金陵科技学院实验报告

实验项目名称： 二叉树 实验学时： 2 同组学生姓名： / 实验地点： A101 实验日期： 2016.5.3 实验成绩： 批改教师： 批改时间：

金陵科技学院实验报告

实验5 二叉树

一、实验目的和要求

（1）掌握二叉树的生成，以及前、中、后序遍历算法。 （2）掌握应用二叉树递归遍历思想解决问题的方法。

二、实验仪器和设备

Turbo C 2.0

三、实验内容与过程（含程序清单及流程图）

1、必做题

（1） 建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出

遍历序列。

（2） 在第一题基础上，求二叉树中叶结点的个数。 （3） 在第一题基础上，求二叉树中结点总数。 （4） 在第一题基础上，求二叉树的深度。 2、选做题

已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。

解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。 程序清单：

#include #include #include

int TWOCHILD; //有两个孩子的结点数 int LEAF; //叶子数 int NODE; //结点数 using namespace std; typedef struct binode{ int data;

struct binode *lchild,*rchild;