数据结构问题什么是树的双亲表示法
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/08/10 03:23:56
数据结构问题什么是树的双亲表示法
![数据结构问题什么是树的双亲表示法](/uploads/image/z/3161737-1-7.jpg?t=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E9%97%AE%E9%A2%98%E4%BB%80%E4%B9%88%E6%98%AF%E6%A0%91%E7%9A%84%E5%8F%8C%E4%BA%B2%E8%A1%A8%E7%A4%BA%E6%B3%95)
从树的定义可知,除根结点外,树中的每个结点都有唯一的一个双亲结点.根据这一特性,可用一组连续的存储空间(一维数组)存储树中的各结点.树中的结点除保存结点本身的信息之外,还要保存其双亲结点在数组中的位置(数组的序号),树的这种表示法称为双亲表示法.
树的双亲表示法对于实现 Parent(t)操作和 Root()操作非常方便.Parent(t)操作可以在常量时间内实现,反复调用Parent(t)操作,
直到遇到无双亲的结点(其
pPos值为-1)时,便找到了树的根,这就是Root()操作的执行过程.但要实现查找孩子结点和兄弟结点等操作非常困难,因为这需要查询整个数组.要实现这些操作,需要在结点结构中增设存放第1个孩子在数组中的序号的域和存放第1个兄弟在数组中的序号的域.
树的双亲表示法对于实现 Parent(t)操作和 Root()操作非常方便.Parent(t)操作可以在常量时间内实现,反复调用Parent(t)操作,
直到遇到无双亲的结点(其
pPos值为-1)时,便找到了树的根,这就是Root()操作的执行过程.但要实现查找孩子结点和兄弟结点等操作非常困难,因为这需要查询整个数组.要实现这些操作,需要在结点结构中增设存放第1个孩子在数组中的序号的域和存放第1个兄弟在数组中的序号的域.