数据结构4树与二叉树.ppt
《数据结构4树与二叉树.ppt》由会员分享,可在线阅读,更多相关《数据结构4树与二叉树.ppt(22页珍藏版)》请在三一办公上搜索。
1、,第6章 树和二叉树,线索二叉树(Threaded Binary),一棵具有n个结点二叉树,用二叉链表表示时,树中存在空指针域的个数为:n+1,利用空指针域指向结点的前驱或后继,结点结构,其中:ltag=0 lchild指向结点的左孩子 ltag=1 lchild指向结点的前驱 rtag=0 rchild指向结点的右孩子 rtag=1 rchild指向结点的后继,以这种结构构成的二叉链表叫线索链表,其中指向前驱和后继的指针称作线索,加上线索的二叉树成为线索二叉树。,二叉树的二叉线索存储表示Typedef enum Link,Thread PointerTag;Typedef struct Bi
2、ThrNode TElemType data;struct BiThrNode*lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;,例如:,中序序列:a+b*c-d-e/f,Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)P=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;while(p-RTag=Thread return OK,中序序列
3、:a+b*c-d-e/f,线索化二叉树,Status InOrderThreading(BiThrTree return OK,void InThreading(BiThrTree p)if(p)InThreading(p-lchild);if(!p-lchild)p-LTag=Thread;p-lchild=pre;if(!pre-rchild)pre-RTag=Thread;pre-rchild=p;pre=p;InThreading(p-rchild);,例:求中序线索树中给定结点的后继结点BiThrTree inordernext(BiThrTree p)if(p-RTag=Threa
4、d)return(p-rchild);else q=p-rchild;while(q-LTag=Link)q=q-lchild;return(q);,6.6 赫夫曼(Huffman)树及其应用,一、赫夫曼(Huffman)树-最优树,路径:从树中一个结点到另一个结点之间的分支构成这 两个结点间的路径,路径长度:路径上的分支数,树的路径长度:从树根到每一个结点的路径长度之和,结点的带权路径长度:该结点到根的路径长度与结点上权的乘积。,树的带权路径长度:树中所有叶子结点的带权路径长度之和。,n记作:wpl=wklk k=1,定义:给定一组权w1 w2 wn,且w1 w2 wn,设有一个二叉树,共有
5、n片叶子,分别带权w1 w2 wn,该二叉树称为带权二叉树。,最优二叉树或Huffman树设有n个权值w1 w2 wn,构造一棵有n个叶子结点的二叉树,每个叶子的权值为wi,则wpl最小的那棵二叉树叫最优二叉树或Huffman树.,例有4个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树,(1)WPL=7*2+5*2+2*2+4*2=36,(2)WPL=4*2+7*3+5*3+2*1=46,(3)WPL=7*1+5*2+2*3+4*3=35,例:将百分制成绩转换成5级分制成绩,if(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b=“gen
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二叉
链接地址:https://www.31ppt.com/p-6296816.html