作业帮数据结构问题什么是树的双亲表示法
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/25 00:10:58
数据结构问题什么是树的双亲表示法
从树的定义可知,除根结点外,树中的每个结点都有唯一的一个双亲结点.根据这一特性,可用一组连续的存储空间（一维数组）存储树中的各结点.树中的结点除保存结点本身的信息之外,还要保存其双亲结点在数组中的位置（数组的序号）,树的这种表示法称为双亲表示法.
树的双亲表示法对于实现 Parent(t)操作和 Root()操作非常方便.Parent(t)操作可以在常量时间内实现,反复调用Parent(t)操作,
直到遇到无双亲的结点（其
pPos值为-1）时,便找到了树的根,这就是Root()操作的执行过程.但要实现查找孩子结点和兄弟结点等操作非常困难,因为这需要查询整个数组.要实现这些操作,需要在结点结构中增设存放第1个孩子在数组中的序号的域和存放第1个兄弟在数组中的序号的域.
树的双亲表示法对于实现 Parent(t)操作和 Root()操作非常方便.Parent(t)操作可以在常量时间内实现,反复调用Parent(t)操作,
直到遇到无双亲的结点（其
pPos值为-1）时,便找到了树的根,这就是Root()操作的执行过程.但要实现查找孩子结点和兄弟结点等操作非常困难,因为这需要查询整个数组.要实现这些操作,需要在结点结构中增设存放第1个孩子在数组中的序号的域和存放第1个兄弟在数组中的序号的域.