Trees

There are many different ways to store data in a computer. Arrays store data linearly, which makes them easy to store in a computer, but often you want a different data structure to organize the data in some manner. This module will cover Trees, a data structure that has many different purposes.

This is a tree:

Terms
A Tree contains individual Nodes, such as "2" and "6", and each Node can point to other Nodes, called child nodes. The Node that points to a child Node is called a parent node. The initial Node in the tree has no parent node and is called a Root node, which is "2" in the above tree. Every other Node has just one parent node, and there are no loops in the Tree. The main tree we'll deal with is a Binary Tree, which is a tree where each Node has a maximum of 2 child Nodes.

A Tree is a Tree

Since a computer cannot just store the above Tree directly, we need a way to implement it for a computer. First, let's precisely define a Binary Tree.

A Binary Tree consists of:

• A node, which contains data, and points to:
• 0,1 or 2 sub-trees, which are also binary trees.

So a Tree is just a Node that points to additional Trees. This is a recursively-define data structure, which means we'll be able to use many Recursive Algorithms when dealing with Trees.

Implementing a Tree

To implement a Tree, we'll create a Node class. It will store an integer of Data, and point to 2 child Nodes.

class Node {

    int data;
    Node left;
    Node right;

}

The above code is actually enough for a basic Tree. The initial Node will form the root of the Tree, and other Nodes can be set as it's children. A Tree is just Nodes that point to other Nodes/Trees.