二叉树作业课件chap6-2014.pptx

下载文档

0
0
约5.15千字
约 30页
2024-09-19 发布于北京
举报
版权申诉
保障服务

二叉树作业课件chap6-2014.pptx

1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

2024/9/161第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.6赫夫曼树及其应用6.6.1最优二叉树(赫夫曼树)

26.4树和森林的表示方法

3树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法

4dataparent结点结构:用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-----存放结点的信息；parent域-----存放该结点双亲结点的位置．6.4.1树的存储结构一、双亲表示法数据双亲

5双亲表示法举例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789数组下标:*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。

6//------------树的双亲表存储表示----------------#defineMAX_TREE_SIZE100typedefstructPTNode{//结点结构TElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{//树结构PTNodenodes[MAX_TREE_SIZE];intr,n;//根的位置和结点数}PTree;

7二、孩子表示法（顺序存储）#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intchild1;//第1个孩子位置域intchild2;//第2个孩子位置域......intchildd;//第d个孩子位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树根结点。

孩子表示法举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。R1A4B0C6D0E0F7G0H0K023500000000089000000

9每个结点的孩子用单链表存储，称为孩子链表。n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。n个孩子链表的头指针用一个向量表示。n个结点的数据和n个孩子链表的头指针又组成一个顺序表。孩子链表存储表示（链式存储）

10//------------树的孩子链表存储表示----------------typedefstructCTNode{//孩子结点intchild;//位置域structCTNode*next;}*ChildPtr;typedefstruct{//孩子链表的头结点TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox；typedefstruct{