老邱二叉树分册.doc

二叉树实验题
实验内容
1. 编写一个程序,实现二叉树的下列运算:
输入一个二叉树的先序序列,生成二叉树的二叉链表;
显示其先序、中序和后序遍历结果
计算二叉树的叶子结点数。
求二叉树的深度
编程实现二叉树的层次遍历
哈夫曼编码
【实验内容】
设某编码系统共有n个字符,使用频率分别为{w1,w2,…,wn},设计一个不等长的编码方案,输出每个字符对应的编码。
【实验要求】
(1)字符个数和相应的权值从终端输入;
(2)具体的输入和输出格式不限。
实验提示
1. 二叉链表定义如下:
typedef char ElemType;
typedef struct bitnode{ //定义二叉树节点结构
ElemType data; //数据域
struct bitnode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
A
F
E
D
C
B
*
*
*
*
*
*
*
如右图:(在空子树处添加*的二叉树的)先序序列:
A B D * F * * * C E * * *
2. 层次遍历的程序实现参考:
1、根结点进队列
2、结点出队列,被访问
3、结点的左、右孩子(非空)进队列
4、反复执行 2、3 ,至队列空为止。
void LevelOrderTraverse(BiTree T)
{// 层次遍历T(利用队列)
if(T) // T不空
{ InitQueue(q); // 初始化队列q
EnQueue(q, T); // 根指针入队
while(!QueueEmpty(q)) // 队列不空
{ DeQueue(q, a); // 出队元素(指针),赋给a
printf(a->data); // 访问a所指结点
if(a->lchild!=NULL) // a有左孩子
EnQueue(q, a->lchild); // 入队a的左孩子
if(a->rchild!=NULL) // a有右孩子
EnQueue(q, a->rchild); // 入队a的右孩子
}
}
}
/*
二叉树实验题
实验内容
1. 编写一个程序,实现二叉树的下列运算:
1)输入一个二叉树的先序序列,生成二叉树的二叉链表;
2)显示其先序、中序和后序遍历结果
3)计算二叉树的叶子结点数。
4)求二叉树的深度
实验提示
1. 二叉链表定义如下:
typedef char ElemType;
typedef struct bitnode{ //定义二叉树节点结构
ElemType data; //数据域
struct bitnode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
如右图:(在空子树处添加*的二叉树的)先序序列:
A B D * F * * * C E * * *
*/
#include <>
#include <>
typedef char SElemType;
typedef struct BiTNode
{
SElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatBiTree(BiTree *T)
{
char c;
cin>>c;
if(c=='*') *T=NULL;
else
{
*T=(BiTNode *)new BiTNode;
(*T)->data =c;
CreatBiTree(&((*T)->lchild ));
CreatBiTree(&((*T)->rchild ));
}
}
void visit(SElemType data)
{
cout<<data<<" ";
}
void PreOrderTraverse(BiTree T)
{
if(T)
{
visit(T->data );
PreOrderTraverse(T->lchild );
PreOrderTraverse(T->rchild );

}
}
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild );
visit(T->data );
InOrderTraverse(T->rchild );
}
}
void Pos