题目内容

给定一个以顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历方式将此部分树（不包含叶子）输出。

只有一个节点的树，此节点认定为根节点（非叶子）。

题解

题目描述

给定一个通过顺序储存结构存储整数值的完全二叉树序列（最多1000个整数），请找出此完全二叉树的所有非叶子节点部分，并采用后序遍历方式将这些节点输出。只有一个节点的树，此节点认定为根节点（非叶子）。

完全二叉树定义

• 完全二叉树是一种每一层都被完全填满，除了最后一层可能不满外，且最后一层的节点都尽量集中在左边的树。
• 对于完全二叉树，父节点和子节点的索引有固定关系：
  • 父节点的索引 i，其左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2。
  • 子节点的父节点索引为 (i-1)/2（向下取整）。