An ordered tree is an oriented tree in which the children of a node are somehow "ordered."

If T_{1} and T_{2} are ordered trees then
T_{1} ≠ T_{2} else
T_{1} = T_{2}.

There are several types of ordered trees:

- k-ary tree
- Binomial tree
- Fibonacci tree

A **Fibonacci Tree** (F_{k}) is defined by

- F
_{0}is the empty tree - F
_{1}is a tree with only one node - F
_{k+2}is a node whose left subtree is a F_{k+1}tree and whose right subtree is a F_{k}tree.

The **Binomial Tree** (B_{k}) consists of a node with
k children. The first child is the root of a B_{k-1} tree,
the second is the root of a B_{k-2} tree, etc.

A k-ary tree is a tree in which the chilren of a node
appear at distinct index positions in 0..k-1. *This means
the maximum number of children for a node is k*.

Some k-ary trees have special names

- 2-ary trees are called
**binary trees**. - 3-ary trees are called
**trinary trees**or**ternary trees**. - 1-ary trees are called
**lists**.

You have to draw k-ary trees carefully. In a binary tree, if a node has one child, you can't draw a vertical line from the parent to the child. Every child in a binary tree is either a left or a right child; that must be made clear.

Since the subtrees of a node are both indexed and bounded, we can use an array for them. Here is an example for a 4-ary tree:

class Node { private Object data; private Node[] children; . . . }

You can also use an array for the whole tree

1 | A |

2 | B |

3 | |

4 | C |

5 | F |

6 | |

7 | |

8 | |

9 | |

10 | |

11 | E |

12 | D |

13 | G |

In a binary tree

- parent(i) is i / 2
- leftChild(i) is 2i
- rightChild(i) is 2i + 1

In a k-ary tree

- parent(i) is (k + i – 2) / k
- jth child of i is ki – (k–2) + j

The array representation may waste a lot of space. The maximally space
efficient k-ary tree is called a **complete tree**. A complete
tree is completely filled out on every level, except perhaps on the last one,
on which all we require is that all its nodes are
"as far to the left as possible." Examples:

Complete trees can be packed into an array with **no** wasted
space at all.

A **perfect k-tree** is a k-ary tree in which every node
is either a 0-node or a k-node and all leaves are on the same level.

Perfect trees are sometimes called **full** trees, though
some people say a full tree is just one in which every node is a 0-node or
a k-node, without caring whether all leaves are on the same level or not.

For k = 2:

Level | Nodes on Level |
Nodes on levels up to and including this one |
---|---|---|

0 | 1 = 2^{0} |
1 = 2^{0+1}–1 |

1 | 2 = 2^{1} |
3 = 2^{1+1}–1 |

2 | 4 = 2^{2} |
7 = 2^{2+1}–1 |

3 | 8 = 2^{3} |
15 = 2^{3+1}–1 |

4 | 16 = 2^{4} |
31 = 2^{4+1}–1 |

h | 2^{h} |
2^{h+1}–1 |

For arbitrary k:

Number of nodes on level h = k^{h}, obviously

Let S(h) = the number of nodes in a perfect binary tree of height h. Let's find a closed form.

S(h) = 1 + k + k^{2}+ k^{3}+ ... + k^{h}k × S(h) = k + k^{2}+ k^{3}+ k^{4}+ ... + k^{h+1}k × S(h) - S(h) = k^{h+1}-1 (k-1) × S(h) = k^{h+1}-1 k^{h+1}- 1 S(h) = --------- k - 1