Download: Trees

A Tree is a non-linear data structure. This means that: (it is also a recursive data structure)

Sometime data can just naturally fall into this type of structure. But it does have an advantage. It has fewer links. This means it take fewer operations to get to the node we need to access.

• It is made of nodes with pointers.
• A node can have more than one pointer.
• A node can connect to more than one other node.

Trees are often used in:

• Manipulating hierarchical data, such as folder structures or movements in a game.
• Making information easy to search. For example, the binary search tree
• Manipulating sorted lists of data.

A tree node has more than one pointer:

Data

Left pointer        |      Right pointer

Each pointer joins more nodes together. They are the address to other nodes.

Binary Tree:

• In a binary tree, each node has no more or fewer than, two pointers.
• The structure of the tree is regular and predictable.

• Root – This is the only node that has no incoming edges.
• Edge – A edge connects two nodes. These are the links between nodes. Every node except the root is connected by exactly one edge from another node. The number of edges is always ‘number of nodes – 1’
• Parent – A node that is a parent of all the nodes it connects to with outgoing edges. This means if two nodes are joined by an edge/link, the upper node is called the parent.
• Child – The set of nodes that have incoming edges from the same node.
• Leaf – A node that has no children. These are the bottom nodes of the tree.
• Subtree – The set of nodes and edges comprised of a parent and all descendants of the parent. A subtree may also be a leaf.

Height: The height of the tree is how far the root node is from the furthest node.

Depth: The depth of a node is the number of links to get back to the root node.

Tree Operations:

Add:	·         Adds new data to the tree. When we add a node, we have to create a new node with given data. We then have to find the place where the new data belongs. Finally, we add a pointer from the parent node to the new node. This connects it to the tree.
Delete:	·         Deletes one item of data from the tree. When we delete a node, we have to first find it and remove the pointer. We then have to think about the children of the deleted node. If we delete the node and not change any of the pointers to the nodes connected to it, then we cannot access them.
Traverse:	·         Visiting every node once only. There are many different ways to traverse a tree.

The Tree in a 2D Array:

We can visualize a tree using circles and lines, but we can also visual it in a 2D Array:

Address	Data	Left	Right
0	F	1	2
1	C	3	Null
2	P	4	Null
3	A	Null	Null
4	J	Null	Null

1. The F node holds the two pointers 1 & 2. The points to the C & P node.
2. The parent node C points to the child node A. The pointer stored in C is 3.
3. A does not have any children; it is a leaf. So it is empty (null)
4. The parent node F points to the child node J. The pointer stored in J is 4.
5. J doesn’t have any children; it is a leaf. So it is empty (null)

Binary Search Tree:

• A Binary Search Tree is used to store data.
• There is certain rule about where each item of data is stored in the tree. This means we can easily find the data we want.
• It is quicker than finding data in a list or an array.

Adding data to a Binary Search Tree:

When adding data to a Binary Search Tree, you look at the root node of the tree and see what is in there. If the value you want to add is smaller, you go to the left of the tree. If it is bigger, you look to the right of the tree.

This is a recursive process. We keep repeating this left-right process until we find an empty space for the data to be added

If the data are numbers, then it sorts them in a numbered order. If the data are text strings, then it stores the data in alphabetical order.

Tree Traversal:

• Traversal is visiting every node. We should not visit any node more than once. This is useful for any processing tasks, for example sending in an email to a group of people.

Breadth-First: – Visiting each node on the same level of a tree before going deeper is an example of a breadth-first search. This is commonly associated with graphs. But a binary tree can also be traversed in this way, buts its implementation does require a queue structure.

• Start at the root node.
• Visit each level from the top and go down level by level.
• Read/traverse the nodes from left to right at each level
• Stop at the bottom of the tree

For Example:

• Traversing this tree example to the left using Breadth-first would be:
• 5, 20, 54, 3, 78, 11

Depth-first search: – This is an algorithm for traversing or searching tree or graph data structures. It is a recursive process.

• Start with the bottom left of the tree.
• Visit each node from left to right to top.
• Work your way up to the finish at the root.

For example:

 

• Traversing this tree example to the using depth-first search would be:
• 3, 6, 20, 78, 21, 11, 54, 5

Types of depth-first search: (not needed for final exam)

• Pre-order traversal – This algorithm can be described as “Node-Left-Right”.

1. Start at the root node.
2. Output the node.
3. Follow the left pointer and repeat from step 2 recursively until there is no pointer to follow.
4. Follow the right pointer and repeat from step 2 recursively until there is no pointer to follow.

• In order traversal – This algorithm can be described as “Left-Node-Right”:

1. Start at the root node.
2. Follow the left pointer and repeat from step 2 recursively until there is no pointer to follow.
3. Output the node.
4. Follow the right pointer and repeat from step 2 recursively until there is no pointer to follow.