二叉树的建立及遍历.doc

文档介绍：《数据结构》实验报告六
二叉树的建立及遍历
班级: 网络班
学号: **********
实验日期:
姓名: 马晓风
程序文件名及说明:
一、实验内容:
要求采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的操作,求所有叶子及结点总数的操作等。具体实现要求:
基于先序遍历的构造算法:输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。
用广义表表示所建二叉树。
用凹入表表示所建二叉树。
分别利用前序遍历、中序遍历、后序遍历所建二叉树。
求二叉树结点总数,观察输出结果。
求二叉树叶子总数,观察输出结果。
交换各结点的左右子树,用广义表表示法显示新的二叉树。
(★)二叉树采用链接存储结构,其根结点指针为T,设计一个算法对这棵二叉树的每个结点赋值:(注意要修改DataType类型)
叶结点的值为3
只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值
左、右孩子均有的结点,则其值等于左、右孩子结点的值之和
用广义表表示法显示所建二叉树
阅读理解建立Huffman树的算法,对该算法进行运行及调试。具体实现要求:
调试并运行Huffman算法,验算《回家作业六》的第3题。
(★)求Huffman树的带权路径长度WPL。
二、实验报告必须写明内容
程序设计的基本思想,原理和算法描述:(包括程序的结构,数据结构,输入/输出设计,符号名说明等)
源程序及注释:
#include <>
#include <>
#include <>
#include <>
#define NULL 0
typedef char DataType;
typedef struct BinTNode
{
DataType data;
struct BinTNode *rchild,*lchild;
}BinTNode,*BinTree;
//创建二叉数
void Create(BinTree *T)
{
char ch;
if((ch = getchar()) == '*') //输入'*'时该节点为空
*T = NULL;
else
{
*T = (BinTree)malloc(sizeof(BinTNode));
(*T)->data = ch;
Create(&(*T)->lchild);
Create(&(*T)->rchild);
}
}
//先序遍历二叉树
void PreOrder(BinTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历二叉树
void InOrder(BinTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
//后序遍历二叉树
void PostOrder(BinTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
//用广义表表示二叉树
void ListPrint(BinTree T)
{
if(T)
{
printf("%c",T->data);
if(T->lchild != NULL || T->rchild != NULL)
{
printf("(");
ListPrint(T->lchild);
if(T->lchild != NULL)
printf(",");
ListPrint(T->rchild);
printf(")");
}
}
}
//用凹入表表示二叉树
/*对于凹入表表示二叉树,其实就是把二叉树结点的深度表示出来*/
void DisplayPrint(BinTree T,int lay)
{
if(T)
{
for(int i=0;i<lay;i++)
printf(" ");
printf("%c\n",T->data);
DisplayPrint(T->lchild,lay+1);
DisplayPrint(T->rchild,lay+1);
}
}