27.10.1. K-ary Tree Implementations¶

\(K\)-ary trees are trees whose internal nodes all have exactly \(K\) children. Thus, a full binary tree is a 2-ary tree. The PR Quadtree discussed in Module 20.1 is an example of a 4-ary tree. Because \(K\)-ary tree nodes have a fixed number of children, unlike general trees, they are relatively easy to implement. In general, \(K\)-ary trees bear many similarities to binary trees, and similar implementations can be used for \(K\)-ary tree nodes. Note that as \(K\) becomes large, the potential number of null pointers grows, and the difference between the required sizes for internal nodes and leaf nodes increases. Thus, as \(K\) becomes larger, the need to choose separate implementations for the internal and leaf nodes becomes more pressing.

Full K-ary trees and complete K-ary trees are analogous to full and complete binary trees, respectively.

Many of the properties of binary trees extend to \(K\)-ary trees. Equivalent theorems to those in Module numref`<BinSpace>` regarding the number of null pointers in a \(K\)-ary tree and the relationship between the number of leaves and the number of internal nodes in a \(K\)-ary tree can be derived. We can also store a complete \(K\)-ary tree in an array, using simple formulas to compute a node's relations in a manner similar to that used in Section 12.16.