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

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

\(\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)+1+i}\)

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

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

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