算法与数据结构实验 14计统一 1413101001 王成

金陵科技学院实验报告

实验5 二叉树

一、实验目的和要求

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

二、实验仪器和设备

Turbo C 2.0

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

1、必做题

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

遍历序列。

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

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

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

#include #include #include

int LEAF=0,JIEDIAN=0,DEPTH=0; typedef struct bitree {

char data;

struct bitree *lc,*rc;

}bitree,*tree;

金陵科技学院实验报告

tree createtree() {

tree t; char x;

scanf(\ if(x=='*')

t=NULL;

else

{

t=(tree)malloc(sizeof(bitree));

t->data=x;

printf(\请输入%c结点的左孩子结点(若没有，请输入 *)\ t->lc=createtree();

printf(\请输入%c结点的右孩子结点(若没有，请输入 *)\ t->rc=createtree();

}

return t; }

void qianxu(tree t) { }

void zhongxu(tree t) {

if(t) {

printf(\

qianxu(t->lc); qianxu(t->rc); }

金陵科技学院实验报告

}

if(t) {

zhongxu(t->lc); printf(\

zhongxu(t->rc); }

void houxu(tree t) { }

void jiedian(tree t) { }

void leaf(tree t) {

if(t) { if(t) {

JIEDIAN++; if(t) {

houxu(t->lc);

houxu(t->rc); }

printf(\

jiedian(t->lc); jiedian(t->rc); }

金陵科技学院实验报告

}

if(t->lc==NULL&&t->rc==NULL) LEAF++;

leaf(t->lc); leaf(t->rc); }

main() {

tree root;

printf(\根节点：\root=createtree(); printf(\前序遍历：\qianxu(root); printf(\

printf(\中序遍历：\zhongxu(root); printf(\

printf(\后序遍历：\houxu(root); printf(\jiedian(root); leaf(root);

DEPTH=(int)(log(JIEDIAN)/log(2)+1); } 2.

#include #include #define maxsize 100

printf(\叶子节点数：%d\\n节点数：%d\\n深度：%d\\n\