k叉树

含 n 个结点的 k 叉树，最小深度为 $\color{blue}{\lfloor log_2[(k-1)n]+1\rfloor} + 1$，最大深度为$\color{blue}$

解析：最小深度即使让前面的所有层是满的，最后一层尽可能满

$\frac{k^{h - 1}-1}{k-1}<n \leq \frac{k^h-1}{k-1}$ $\Rightarrow$ $h-1<log_k[n(k-1)+1]\leq h$

最大深度即使每一层都只有一个元素

满 k 叉树，根的编号为 1

1. 求 p 的第 i 个孩子的编号$\color{blue}$

解析：k (p-1) 表示前 p-1 个结点所拥有的所有孩子的数量，即 p 的第 1 个孩子之前的所有孩子的数量（除了根节点不是任何节点的孩子），加一加的是根节点

2. p 的父亲节点的编号$\color{blue}{\lfloor \frac{p+(k-2)}{k}\rfloor}$

解析：观察发现 k 叉树中每个节点的子节点的后面两个节点的编号除以 k 为父节点的编号，倒数第 2 个叉的编号是父节点的 k 倍