树是一种什么结构 树 - 树和森林- 树的存储结构（一）

树 - 树和森林- 树的存储结构（一）  

　　本节仅讨论树的三种常用表示法

　　 双亲链表表示法

　　双亲链表表示法利用树中每个结点的双亲唯一性 在存储结点信息的同时 为每个结点附设一个指向其双亲的指针parent 惟一

　　地表示任何 棵树

　　( )双亲链表表示法的实现

　　方法① 用动态链表实现

　　方法② 用向量表示——更为方便

　　( )双亲链表向量表示的形式说明

　　#define MaxTreeSize //向量空间的大小 由用户定义

　　typedef char DataType; //应由用户定义

　　typedef struct{

　　DataType data;//结点数据

　　int parent; //双亲指针 指示结点的双亲在向量中的位置

　　}PTreeNode;

　　typedef struct{

　　PTreeNode nodes[MaxTreeSize];

　　int n; //结点总数

　　}PTree;

　　PTree T; //T是双亲链表

　　注意

　　若T nodes[i] parent=j 则T nodes[i]的双亲是T nodes[j]

　　( )双亲链表表示实例

　　【例】图 (a)的双亲链表表示如下面数组所示

　　分析

　　E和F所在结点的双亲域是 它们的双亲结点在向量中的位置是 即B是它们的双亲

　　注意

　　① 根无双亲 其parent域为

　　② 双亲链表表示法中指针parent向上链接 适合求指定结点的双亲或祖先(包括根);求指定结点的孩子或其它后代时 可能要

　　遍历整个数组