数据结构二叉树.doc

常熟理工学院《数据结构与算法》实验指导与报告书_2017-2018_____学年第__1__学期专业:物联网工程实验名称:二叉树实验地点:N6-210指导教师:聂盼红计算机科学与工程学院2017实验六二叉树【实验目的】1、掌握二叉树的基本存储表示。2、掌握二叉树的遍历操作实现方法(递归和非递归方法)。3、理解并实现二叉树的其他基本操作。4、掌握二叉树的重要应用---哈夫曼编码的实现。【实验学时】4-6学时【实验预****回答以下问题:1、二叉树的二叉链表存储表示。/*---二叉树的二叉链表存储表示---*/typedefstructBTNode{chardata;/*结点数据*/structBTNode*lchild;/*左孩子指针*/structBTNode*rchild;/*右孩子指针*/}*BiTree;2、二叉树的三种基本遍历方式。/*先序遍历二叉树,补充递归算法*/voidPreOrder(BiTreep){if(p!=NULL);{printf("%c",p->data);//访问根节点PreOrder(p->lchild);//先序遍历左子数PreOrder(p->rchild);//先序遍历右子数}}/*PreOrder*//*中序遍历二叉树,补充递归算法*/voidInOrder(BiTreep){if(p!=NULL);{InOrder(p->lchild);//中序遍历左子数printf("%c",p->data);//访问根节点InOrder(p->rchild);//中序遍历右子数}}/*InOrder*//*后序遍历二叉树,补充递归算法*/voidPostOrder(BiTreep){if(p!=NULL);{PostOrder(p->lchild);//后序遍历左子数PostOrder(p->rchild);//后序遍历右子数printf("%c",p->data);//访问根节点}}/*PostOrder*/3、解释哈夫曼树和带权路径长度WPL。 哈夫曼树,是指权值为W1、W2、….Wn的n个叶节点所构成的二叉树中带权路径长度最小的二叉树。从树根结点到到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度,通常记作:WPL=Σ(n,i=1)WiLi【实验容和要求】,实现二叉树的链式存储及基本操作。以下图所示的二叉树实现二叉树的二叉链表存储及基本操作,回答下列问题,补充完整程序,并调试运行验证结果。(1)按照先序序列建立该二叉树。读入的字符序列应为:A,B,C,*,*,D,E,*,G,*,*,F,*,*,*(*表示空指针)。(2)该二叉树的三种遍历序列:先序序列:A,B,C,D,E,G,F;中序序列:C,B,E,G,D,F,A;后序序列:C,G,E,F,D,B,A;(3)按层次遍历该二叉树,得到的序列为:A,B,C,D,E,F,G(4)该二叉树的深度为5。(5)该二叉树的叶子结点数为:______3_____。A(6)交换该二叉树所有结点的左右次序得到的新二叉树为:(画出新二叉树的图)BCDEFG(7)新二叉树的三种遍历序列分别为:先序序列:A,B,D,C,F,G,E;中序序列:D,B,F,G,C,E,A;后序序列:D,G,F,E,C,B,A;:#include<>#include<>#defineMAX20/*---二叉树的二叉链表存储表示---*/typedefstructBTNode{chardata;/*结点数据*/structBTNode*lchild;/*左孩子指针*/structBTNode*rchild;/*右孩子指针*/}*BiTree;/*---非递归遍历辅助队列---*/typedefstructSqQueue{BiTreedata[MAX];intfront,rear;}SqQueue;voidcreateBiTree(BiTree*t); /*先序遍历创建二叉树*/voidPreOrder(BiTreep); /*先序遍历二叉树*/voidInOrder(BiTreep); /*中序遍历二叉树*/voidPostOrder(BiTreep); /*后序遍历二叉树*/voidRPreorder(BiTreep); /*先序遍历的非递归算法*/voidRInorder(BiTreep); /*中序遍历的非递归算法*/voidRPostorder(BiTreep); /*后序遍历的非递归算法*/intdepth(BiTreet); /*求二叉树的深度算法*/BiTreegettreenode(charx,BiTreelptr,BiTreerptr);/*后序复制二叉树-建立结点*/BiTree