关于数据结构的树的问题.

Question

一棵高度为 h 的满 k 叉树有如下性质:第 h 层上的结点都是叶结点,其余各层上每个结点都有 k 棵非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进行编号,试问: 编号为i 的结点的父结点(若存在)的编号是多少? 
能不能帮我详细推导一下.谢谢.

Answer 1

第一层有1个结点，第二层有k个结点，，第h层有k^(h-1)（k的h-1次方）个结点。
判断i落在哪个区间。
不失一般性，设k^(m-1) < i <= k^m，即i在第m+1层，
则j = i - k^(m-1)，
n = k^(m-2) + j / k，
n即为k的父结点的编号

Answer 2

谢谢..我知道思路了.但我怎么觉得求 i 的时候, i 应该大于 前 m 层 的总数和,小于 m+1 层的 总数和?