m-ary tree

For traversing in-order, since there are more than two children per node for m > 2, one must define the notion of left and right subtrees.

One common method to establish left/right subtrees is to divide the list of children nodes into two groups.

Using an array for representing a m-ary tree is inefficient, because most of the nodes in practical applications contain less than m children.

As a result, this fact leads to a sparse array with large unused space in the memory.

(assuming the root has index zero, meaning a 0-based array).

This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal.

Listing all possible m-ary trees is useful in many disciplines as a way of checking hypotheses or theories.

Proper representation of m-ary tree objects can greatly simplify the generation process.

One can construct a bit sequence representation using the depth-first search of a m-ary tree with n nodes indicating the presence of a node at a given index using binary values.

For example, the bit sequence x=1110000100010001000 is representing a 3-ary tree with n=6 nodes as shown below.

Therefore, enumeration over binary strings would not necessarily result in an ordered generation of all m-ary trees.

where j is the number of zeroes needed at the tail end of the sequence to make the string have the appropriate length.

, which is called zero sequence, which duplicate bases cannot be adjacent.

That is to say that number of zeros in the bit sequence of a m-ary tree cannot exceed the total number of null pointers (i.e., pointers without any child node attached to them).

without creating an invalid structure (i.e. having an available null pointer to attached the last node to it).

The table below shows the list of all valid simple zero sequences of all 3-ary trees with 4 nodes: Starting from the bottom right of the table (i.e., "000"), there is a backbone template that governs the generation of the possible ordered trees starting from "000" to "006".

The backbone template for this group ("00X") is depicted below, where an additional node is added in the positions labeled "x".

, we can easily observe the apparent jump from "006" to "010" can be explained trivially in an algorithmic fashion as depicted below: The pseudocode for this enumeration is given below:[7] A generation algorithm that takes

is promoted to root, as shown below: A right-t rotation at d is the inverse of this operation.

Any m-ary tree can be transformed to a left-chain tree using sequence of finite left-t rotations for t from 2 to m. Specifically, this can be done by performing left-t rotations on each node

Then, the sequence of number of left-t rotations performed at depth i denoted by

defines a codeword of a m-ary tree that can be recovered by performing the same sequence of right-t rotations.

Thus, enumerating all possible legal encoding would helps us to generate all the m-ary trees for a given m and n. But, not all

sequences of m non-negative integers represent a valid m-ary tree.

non-negative integers is a valid representation of a m-ary tree if and only if[8]

One of the applications of m-ary tree is creating a dictionary for validation of acceptable strings.

In order to do that, let m be equal to the number of valid alphabets (e.g., number of letters of the English alphabet) with the root of the tree representing the starting point.

For example, in the example below "at" and "and" are valid key strings with "t" and "d" marked as terminal nodes.

Terminal nodes can store extra information to be associated with a given key.

There are similar ways to building such a dictionary using B-tree, Octree and/or trie.