10. K 叉树实现¶
10.1. K 叉树实现¶
\(K\) 叉树是内部结点恰好都有 \(K\) 个孩子的树。
因此，满二叉树就是 2 叉树。
在模块 <Spatial> 中讨论的 PR 四叉树就是一个 4 叉树的例子。
由于 \(K\) 叉树的结点有固定数量的孩子，与一般树不同，
它们相对容易实现。
一般来说，\(K\) 叉树与二叉树有许多相似之处，
可以为 \(K\) 叉树的结点采用类似的实现。
注意，随着 \(K\) 变大，可能出现的 null 指针数量会增多，
内部结点与叶结点所需大小的差异也会增大。
因此，随着 \(K\) 变大，
为内部结点和叶结点选择不同实现的需求也变得更为迫切。
满 K 叉树和完全 K 叉树分别与满二叉树和完全二叉树类似。
待处理
- type: Slideshow
图书图表 6.16 的幻灯片：展示 K=3 时的满 Kary树和完全 Kary树。 在实践中，Kary树的大多数应用都把它们限制为满树或完全树。
满 3 叉树和完全 3 叉树。 (a)~这棵树是满树（但不是完全树）。 (b)~这棵树是完全树（但不是满树）。}{ThreeTree}
二叉树的许多性质可以推广到 \(K\) 叉树。
可以推导出与模块 numref`<BinSpace>` 中关于 \(K\) 叉树中
null 指针数量、以及 \(K\) 叉树叶结点与内部结点数量关系的
定理等价的结果。
我们还可以把一棵完全 \(K\) 叉树存储在数组中，
使用简单的公式来计算结点的各种关系，
方式与 <CompleteTree> 节中所用方法类似。
