Binary trees
A Binary Tree is another Data Structure. It is a heirarchical structure where every parent node can have a maximum of two child nodes (which is why it's called a binary tree).
Let's return to the idea of storing data in some kind of order, for example storing integers in an array:
| 13 | 7 | 5 | 9 | 11 | 18 | 16 | 21 |
Here is the above array sorted visually into a binary tree:
There is a root node at the top.
There are more nodes beneath the root node.
Some nodes have child nodes.
Some nodes do not have any child nodes. These are leaf nodes.
Each Node has:
- data
- a left pointer
- a right pointer
Here is what a node might look like, along with its pseudocode definition:
TYPE Node
DECLARE data : INTEGER
DECLARE leftPointer : INTEGER
DECLARE rightPointer : INTEGER
END TYPE
We could conceptualize that we have an array of Nodes. Imagine that this is an array of Nodes (for simplicity, we can only see the data item in each node):
| 13 | 7 | 5 | 9 | 11 | 18 | 16 | 21 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Then we could visualize a binary tree as follows:
If a Node has no right-child and/or left-child, then its pointer values will be -1 or NULL or something to indicate this situation.
When inserting a node into a binary tree, we compare the data in the new node with nodes already in the tree. We keep comparing until we reach a null pointer. This will be the location to insert the new node.
When comparing the new data with the data in nodes in the tree, if the new data is less than the Node data, we follow the left pointer, otherwise we follow the right pointer.
The algorithm for inserting an item into the above tree (implemented on a 1D array) is:
#set a pointer to the root node
currentPointer ← 0
#assign the new node to the free pointer element
arr[freepointer] ← newItem
WHILE currentPointer <> -1 DO
trailingPointer ← currentPointer
IF item < arr[currentPointer].data
THEN
currentPointer ← arr[currentPointer].leftPointer
ELSE
currentPointer ← arr[currentPointer].rightPointer
END WHILE
IF newItem.data < arr[trailingPointer].data THEN
arr[trailingPointer].leftPointer ← freePointer
ELSE
arr[trailingPointer].rightPointer ← freePointer
freePointer ← freePointer+1
Here is a simulation. Follow these steps.
- press ESC on your keyboard to close the selection window.
- Choose Create and then Empty
- Choose insert and type one number into the input box
- Continue to insert 1 value into the tree
Can you see how it works?