题干为树（不是二叉树）的存储形式，有3中常用的存储结构：①双亲表示法；②孩子表示法；③孩子兄弟表示法
树的存储方式有多种，既可以采用顺序存储，也可以采用链式存储，D选项无“顺序存储表示法”这一说法
【以下摘自王道2019数据结构】【https://pan.baidu.com/s/1iXinl2bjuGjCx3U10BVODw】
1、双亲表示法
【概念】采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置，根结点下标为0，其伪指针域为-1（可以用结构体数组实现）
【优点】可以很快得到每个结点的双亲结点
【缺点】求结点的孩子时需要遍历整个结构
2、孩子表示法
【概念】将每个结点的孩子结点都用单链表链接起来形成一个线性结构，则 N 个结点就有 N 个孩子链表（叶子结点的孩子链表为空表）
【优点】可以很快找到某个结点的所有子女（遍历该结点的孩子链表即可，比如 D：1（S），2（E），3（G））
【缺点】寻找双亲操作需要遍历每个结点的孩子链表
3、孩子兄弟表示法
【概念】孩子兄弟表示法又称为二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法每个结点包括三部分内容：①结点值；②指向结点第一个孩子的指针；③指向结点下一个兄弟的指针（沿此域可以找到结点的所有兄弟结点）
【优点】存储灵活，树转换为二叉树操作实现方便，易于查找结点的孩子等
【缺点】不易从当前结点查找其双亲结点（可以为每个结点增设一个 parent 域指向其父亲结点，但需要额外的空间开销）
发表于 2018-11-28 16:59:31
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
