上海建工网站,广州seo技术外包公司,建设网站所需材料,ui界面设计培训班数据结构—基础知识#xff08;13#xff09;#xff1a;树的存储结构 双亲表示法 这种表示方法中#xff0c;以一组连续的存储单元存储树的结点#xff0c;每个结点除了数据域data外#xff0c;还附设一个parent域用以指示其双亲结点的位置。 这种存储结构利用了每个结…数据结构—基础知识13树的存储结构 双亲表示法 这种表示方法中以一组连续的存储单元存储树的结点每个结点除了数据域data外还附设一个parent域用以指示其双亲结点的位置。 这种存储结构利用了每个结点除根结点外只有唯一的双亲性质。这种存储结构下求结点的双亲十分方便也很容易求树的根但求结点的孩子时需要遍历整个结构。 孩子表示法 由于树中每个结点可能有多棵子树则可用多重链表即每个结点有多个指针域其中每个指针指向一棵子树的根结点此时链表中的结点可以有如下图的两种结点格式。 若采用第一种结点格式则多重链表中的结点是同构的其中d为树的度。由于树中很多结点的度小于 d所以链表中有很多空链域空间较浪费不难推出在一棵有n个结点度为k的树中必有n(k-1)1 个空链域。 若采用第二种结点格式则多重链表中的结点是不同构的其中d为结点的度degree 域的值同d。此时虽能节约存储空间但操作不方便。 另一种办法是把每个结点的孩子结点排列起来看成是一个线性表且以单链表做存储结构则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表为了便于查找可采用顺序存储结构。 下图(a)所示为下图中的树的孩子表示法。与双亲表示法相反孩子表示法便于那些涉及孩子的操作的实现。可以把双亲表示法和孩子表示法结合起来即将双亲表示和孩子链表合在一起。图(b)所示的就是这种存储结构的一例它和图(a)表示的是同一棵树。 孩子兄弟法 孩子兄弟法又称二叉树表示法或者二叉链表表示法即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点(firstchild)和下一个兄弟结点(nextsibling) //------树的二叉链表孩子—兄弟存储表示------
typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
