10 Data Structures

10.6 Binary Trees

A tree is a dynamic data structure with hieracally organised nodes.

• There is a root node at the beginning of the tree structure.
• Every node except the root node has one parent.
• Childless nodes are called leaf nodes or terminal nodes.

Every tre has only one root, but each node in the tree can be regarded as the root of a sub-tree.

A binary tree is a special type of tree. Each parent can have no more than children.

Example - Decoding Morse Code

Starting from the root move right if "-" or left if it is a ".".

10.6.1 Constructing A Binary Search Tree

A search tree is an application of a binary tree. It allows the tree to be searched.

We can store a list of names (or any other data) in a binary tree.

We are given a list of names in no particular order.

Example

Legg, Charlesworth, Illman, Hawthorne, Todd, Youngman, Jones, Ravage

Then to create a binary search tree that can be searched we:

• Place the first item in the root.
• Insert the items in the order that they are given.
• The item is added after the left branch if it comes before the previous node in the alphabetic or numeric sequence.
• or the item is added after the right branch if it comes after the last node in the alphabetic or numeric sequence.

10.6.2 Traversing A Binary Search Tree

One important use of binary search trees is to rapidly retrieve a single data item.

All the data items can be extracted in a number of different sequences.

The traversal algorithms (that extract data in these different sequences) are recursive.

Traversal Algorithms

Preorder Traversal

• Start at the root.
• Traverse the left-hand subtree.
• Traverse the right-hand subtree.

The nodes are visited in the order:

D - B - A - C - F - E - G

Inorder Traversal

• Traverse the left-hand subtree.
• Visit the root.
• Traverse the right-hand subtree.

The nodes are visited in the order:

A - B - C - D - E - F - G

Postorder Traversal

• Traverse the left-hand subtree.
• Traverse the right-hand subtree.
• Return to the root.

The nodes are visited in the order:

A - C - B - E - G - F - D

10.6.3 Implementation Of Binary Search Trees Using Arrays

Binary trees can be implemented using left and right pointers at each node.

Left Child Node Index	Value	Right Child Node Index
2	Legg	5
0	Charlesworth	3
4	Illman	7
0	Hawthorne	0
8	Todd	6
0	Youngman	0
6	Jones	0
0	Ravage	0

---

< Previous

Back To Topic

Next >

---