树的存储结构
树的存储结构
双亲表示法
由树的定义可知，树中的每个节点都有且仅有一个双亲结点。根据这一特性，可以用一维数组来存储树的各个结点（一般按照层序存储），数组中的一个元素对应树中的一个结点，数组元素包括树中结点的数据信息以及该结点的双亲在数组中的下标。有①双亲表示法和②带有兄弟的双亲表示法两种常用结构。
孩子表示法
树的孩子表示法是一种基于链表的存储方式，主要形式有两种①多重链表表示法、②孩子链表表示法
多重链表表示法：
其中，首位存的是当前结点的值，后面是存孩子的地址，长度为树的度。
孩子链表表示法：
双亲孩子表示法
双亲孩子表示法是将双亲表示法和孩子链表表示法相结合的存储方法。
孩子兄弟表示法
树的孩子兄弟表示法又称为二叉链表表示法，其方法是链表中每个结点除数据域外，还设了两个指针分别指向该结点的第一个孩子和有兄弟。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OsYo4Mku-1605013730124)(C:\Users\Rin\AppData\Roaming\Typora\typora-user-images\image-20201110210755177.png)]