4-3树的存储结构

4-3树的存储结构v第四章树和二叉树思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系数据元素及其逻辑关系在存储器中的表示实现树的存储结构，关键是什么?什么是存储结构?树中结点之间的逻辑关系是什么?CBGFEDHIA学什么？4-3-1树的双亲表示法v第四章树和二叉树双亲表示法CBGFEDHIA树的双亲表示法：用一维数组存储树中各个结点（一般按层序存储）的数据信息以及该结点的双亲在数组中的下标012345678dataparent

ABCDEFGHI

-100111224如何定义树的双亲表示法?template<typename

DataType>struct

PNode

{

DataTypedata;

intparent;};012345678

A-1B0C0D1E1F1G2H2I

4dataparent如何查找双亲结点？时间性能？O(1)如何查找孩子结点？时间性能？O(n)数据表示firstChild

136

-18-1-1-1-1双亲表示法CBGFEDHIA4-3-2树的孩子表示法v第四章树和二叉树孩子表示法CBGFEDHIA如何表示结点的孩子呢？方案一：指针域的个数等于树的度

datachild1child2……childd其中：data：数据域，存放该结点的数据信息

child1~childd：指针域，指向该结点的孩子∧AB∧C∧D∧E∧F∧G∧H∧I∧∧∧∧∧∧∧∧∧∧∧缺点：浪费空间CBGFEDHIA方案二：指针域的个数等于该结点的度

datadegreechild1child2……childd其中：data：存放该结点的数据；degree：存放该结点的度；

child1~childd：指针域，指向该结点的孩子孩子表示法如何表示结点的孩子呢？A2B3C2E1I0G0H0F0D0缺点：结点结构不一致CBGFEDHIA方案三：将结点的所有孩子构成一个单链表12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdata孩子表示法如何表示结点的孩子呢？如何定义树的孩子表示法呢？12∧345∧7∧68∧∧∧∧∧∧firstChild

012345678

ABCDEFGHIdatachildnext孩子结点datafirstChild表头结点孩子表示法structChildNode//孩子结点{

intchild;ChildNode*next;};template<typenameDataType>structTreeNode//表头结点{DataTypedata;ChildNode*firstChild;//指向孩子链表的头指针};如何定义树的孩子表示法呢？孩子表示法childnext孩子结点datafirstChild表头结点ACBGFEDHI如何查找孩子结点？时间性能？O(1)12∧345∧7∧68∧∧∧∧∧∧firstchild

012345678

ABCDEFGHIdata孩子表示法ACBGFEDHI如何查找双亲结点？时间性能？O(n)12∧345∧7∧68∧∧∧∧∧∧firstchild

ABCDEFGHIdata012345678

ABCDEFGHIdata

parent-100111224孩子表示法4-3-3树的孩子兄弟表示法v第四章树和二叉树孩子兄弟表示法CBGFEDHIA树的孩子兄弟表示法（二叉链表）：链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针某结点的第一个孩子是惟一的某结点的右兄弟是惟一的设置两个分别指向该结点的第一个孩子和右兄弟的指针CBGFEDHIA

B∧

D

C

F

I

G∧

H∧

E∧∧∧∧∧∧∧

A孩子兄弟表示法树的孩子兄弟表示法（二叉链表）：链表中的每个结点包括数据域和分别指向该结点的第一个孩子和右兄弟的指针如何定义树的孩子兄弟存储结构?firstChilddata

rightSibtemplate<typenameDataType>structTNode{

DataTypedata;

TNode<DataType>*firstChild,*rightSib;};

孩子兄弟表示法

A

B

C

D

E

F

G

H

I∧∧∧∧∧∧∧∧∧∧ACBGF