问答题 一棵含有n个结点的k叉树,可能达到的最大深度和最小深度各为多少?
【正确答案】一棵含有n个结点的k叉树,如果构造成每一层都只有一个结点的树,则其达到的深度为最大,即深度为n;而一棵含有n个结点的k叉树,如果构造成完全k叉树的话,其深度为最小,即[logkn(k-1)]+1。
   推导过程如下:
   设一个完全k叉树的深度为L,则前L-1层是满k叉树,设参数mL-1为满k叉树从第1层到第L-1层的总结点数,则有
   mL-1=1+k+k2+…+kL-2=(kL-1-1)/(k-1)
   就有(kL-1-1)/(k-1)<n≤(kL-1)/(k-1)
   kL-1-1<n(k-1)≤kL-1
   kL-1≤n(k-1)<kL
   对此式两边同时取对数有:L-1≤logkn(k-1)<L
   因为L是整数,所以有:L-1=[logkn(k-1)]
   最后得:L=[logkn(k-1)]+1
【答案解析】