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

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{