第1个回答 2011-05-15
实验报告
实验名称：遍历二叉树
实验目的：
掌握二叉树链式存储的类型定义及实现。
掌握二叉树链式存储的各类基本运算方法
掌握二叉树用不同方法标识所对应的不同输入形式。
掌握二叉树中各个重要性质在解决实际问题中的应用。
掌握二叉树的分析方法，解决方法，从而提高实际编程能力及程序调试能力等。
实验要求:
建立一个二叉树并对其进行遍历
实验内容
1、创建二叉树
2、用递归方法实现二叉树的各种遍历
实验仪器与设备
计算机、VC++6.0程序
实验原理
建立一个二叉树，利用递归的方法实现对该二叉树的遍历，并输出遍历结果。
实验程序及结果
#include"stdlib.h"
#include"stdio.h"
#include"malloc.h"
#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
typedef char DataType;
typedef struct Node
{
DataType 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));
}
return;
}
/*采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左右子树的叶子结点数之和*/
int leaf(BiTree bt)
{
int LeafCount;
if(bt==NULL)
LeafCount =0;
else if((bt->LChild==NULL)&&(bt->RChild==NULL))
LeafCount=1;
else
LeafCount=leaf(bt->LChild)+leaf(bt->RChild);
return LeafCount;
}
void PrintTree(BiTree bt,int nLayer) /*按竖向树状打印二叉树*/
{
if(bt==NULL)return;
PrintTree(bt->RChild,nLayer+1);
for(int i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",bt->data);
PrintTree(bt->LChild,nLayer+1);
}
void main() /*调用主函数连接其他函数，构成完整的程序*/
{
BiTree bt;
printf("请输入二叉树的序列: \n");
CreateBiTree(&bt);
printf("该二叉树的叶子结点个数为: %d\n",leaf(bt));
printf("该二叉树的形状为：\n");
int nLayer=0;
PrintTree(bt,nLayer);
}
请输入数据：AB.DF..G..C.E.H..
结果：
实验总结：
通过学习数据结构，发现数据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和广义表是对线性表的扩展：表中的数据元素本身也是一个数据结构。除了线性表以外，栈是重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。树状结构中的重点自然是二叉树和哈弗曼树了。对于二叉树的很多操作都是基于对二叉树的遍历，掌握了如何遍历，很多问题也就迎刃而解了，比如对二叉树结点的查找访问、统计二叉树中叶子结点的数目、求二叉树的深度等。哈弗曼编码也有着很广泛的应用。对于图状结构，主要学习图的存储结构及图的遍历。
学习算法的目的是利用算法解决实际问题。会写课本上已有的算法之后，可以借其思想进行扩展，逐步提高编程能力。比如数值转换，括号匹配的检验，检验平衡二叉树等。本回答被网友采纳