《数据结构与算法》实验指导V2016 实验六 二叉树
【实验目的】
1、掌握二叉树的基本存储表示。
2、掌握二叉树的遍历操作实现方法（递归和非递归方法）。 3、理解并实现二叉树的其他基本操作。
4、掌握二叉树的重要应用---哈夫曼编码的实现。
【实验学时】
4-6学时
【实验预习】
回答以下问题：
1、二叉树的二叉链表存储表示。 typedef struct BiTNode{ // 结点结构
ElemType data ；//数据域
struct BiTNode *Lchild ；//左孩子指针 struct BiTNode *Rchild；//右孩子指针 } BiTNode ，*BiTree ； void Create(BiTree &T)
{//输入扩展二叉树的先序序列，构建二叉链表 scanf(&ch); //输入一个元素 if (ch=='# ') T = NULL; else
{ T= (BiTree)malloc(sizeof(BiTNode))；
//申请根结点
T->data =ch; // 给根结点数据域赋值 Create(T->Lchild);//建左子树
Create(T->Rchild);//建右子树 } } // Create
2、二叉树的三种基本遍历方式。 （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 常熟理工学院计算机科学与工程学院
1
《数据结构与算法》实验指导V2016
3、解释哈夫曼树和带权路径长度WPL。 哈夫曼树：
它是最优二叉树。
定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。
路径和路径长度 定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
结点的权及带权路径长度
定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
【实验内容和要求】
1、 编写程序exp6_1.c，实现二叉树的链式存储及基本操作。 以下图所示的二叉树实现二叉树的二叉链表存储及基本操作，回答下列问题，补充完整程序，并调试运行验证结果。
ABCEG∧G∧DF∧E∧F∧∧C∧BDA∧ （1）按照先序序列建立该二叉树。
读入的字符序列应为：________ABCDEFG_________________(*表示空指针)。 （2）该二叉树的三种遍历序列：
先序序列：__ABCDEFG______________; 中序序列：__CBEGDFA______________; 后序序列：__CGEFDBA______________;
（3）按层次遍历该二叉树，得到的序列为：_____ABCDEFG_______。 （4）该二叉树的深度为：__4______。
（5）该二叉树的叶子结点数为：____3_______。
（6）交换该二叉树所有结点的左右次序得到的新二叉树为：（画出新二叉树的图）
常熟理工学院计算机科学与工程学院
2
《数据结构与算法》实验指导V2016 A B D C F E G （7）新二叉树的三种遍历序列分别为：
先序序列：____ABDFEGC______________________; 中序序列：____AFDGEBC______________________; 后序序列：____FGEDCBA______________________;
exp6_1.c参考程序如下： #include
/*---二叉树的二叉链表存储表示---*/ typedef struct BTNode {
char data ; /*结点数据*/ struct BTNode *lchild; /*左孩子指针*/ struct BTNode *rchild ; /*右孩子指针*/ }*BiTree;
/*---非递归遍历辅助队列---*/ typedef struct {
BiTree data[MAX]; int front,rear; } queue;
void createBiTree(BiTree *t); /*先序遍历创建二叉树*/ void PreOrder(BiTree p); /*先序遍历二叉树*/ void InOrder(BiTree p); /*中序遍历二叉树*/ void PostOrder(BiTree p); /*后序遍历二叉树*/ void RPreorder(BiTree p); /*先序遍历的非递归算法*/ void RInorder(BiTree p); /*中序遍历的非递归算法*/ void RPostorder(BiTree p); /*后序遍历的非递归算法*/
常熟理工学院计算机科学与工程学院
3
《数据结构与算法》实验指导V2016 int depth(BiTree t); /*求二叉树的深度算法*/
BiTree gettreenode(char x,BiTree lptr,BiTree rptr);/*后序复制二叉树-建立结点*/ BiTree copytree(BiTree t); /*以后序遍历的方式复制二叉树*/ BiTree swap(BiTree b); /*交换二叉树的结点的左右孩子*/ void ccOrder(BiTree t); /*利用循环队列实现层次遍历*/ int Leaves(BiTree t); /*统计二叉树叶子结点（递归）*/ void release(BiTree t); /*释放二叉树*/
/*先序遍历创建二叉树*/ void createBiTree(BiTree *t) {
char s; BiTree q;
printf(\ s=getchar();
getchar(); /*扔掉存在键盘缓冲区的输入结束回车符*/ if(s=='#') /*子树为空则返回*/ {
*t=NULL; return; }
q=(BiTree)malloc(sizeof(struct BTNode)); if(q==NULL) {
printf(\ exit(0); }
q->data=s; *t=q;
createBiTree(&q->lchild);/*递归建立左子树*/ createBiTree(&q->rchild);/*递归建立右子树*/ }/*createBiTree*/
/*先序遍历二叉树，补充递归算法*/ void PreOrder(BiTree p) {
if(p!=NULL)
{ printf(\ PreOrder (p->lchild);
PreOrder (p->rchild); }
常熟理工学院计算机科学与工程学院
4
《数据结构与算法》实验指导V2016 }/*PreOrder*/
/*中序遍历二叉树，补充递归算法*/ void InOrder(BiTree p) {
if(p!=NULL) { InOrder (p->lchild);
printf(\ InOrder (p->rchild); }
}/*InOrder*/
/*后序遍历二叉树，补充递归算法*/ void PostOrder(BiTree p) {
if(p!=NULL)
{ PostOrder (p->lchild):
PostOrder (p->rchild); printf(\ }
}/*PostOrder*/
/*先序遍历的非递归算法*/ void RPreorder(BiTree p) {
BiTree stack[MAX],q; int top=0,i;
for(i=0; i while(q!=NULL) { printf(\ if(q->rchild!=NULL) _____stack[top++]=q->rchild_____; /*右指针进栈*/ if(q->lchild!=NULL) q=q->lchild; /*顺着左指针继续向下*/ else if(top>0) q=stack[--top]; /*左子树访问完，出栈继续访问右子树结点*/ else q=NULL; } }/*RPreorder*/ /*中序遍历的非递归算法*/ 常熟理工学院计算机科学与工程学院 5 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构实验报告6-二叉树与哈夫曼树在线全文阅读。
相关推荐：