Ordered Trees

Definition

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

If T₁ and T₂ are ordered trees then T₁ ≠ T₂ else T₁ = T₂.

Types of Ordered Trees

There are several types of ordered trees:

k-ary tree
Binomial tree
Fibonacci tree

Fibonoacci Trees

A Fibonacci Tree (F_k) is defined by

F₀ is the empty tree
F₁ 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.

Exercise: Draw the trees F₀ through F₅.

Binomial Trees

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.

Exercise: Draw the trees B₀ through B₅.

k-ary Trees

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.

Representations of k-ary Trees

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

Exercise: Prove each of these statements.

Complete k-ary Trees

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.

Perfect Trees

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.

The Size of k-ary Trees

For k = 2:

Level	Nodes on Level	Nodes on levels up to and including this one
0	1 = 2⁰	1 = 2⁰⁺¹–1
1	2 = 2¹	3 = 2¹⁺¹–1
2	4 = 2²	7 = 2²⁺¹–1
3	8 = 2³	15 = 2³⁺¹–1
4	16 = 2⁴	31 = 2⁴⁺¹–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² + k³ + ... + k^h

    k × S(h) = k + k² + k³ + k⁴ + ... + 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