Algorithms – Trees
January 8, 2010 Leave a comment
So what exactly is a Tree in programming?
Well, it is not a tree that you see every day when you walk through a park 😛
A tree in programming is similar to an actually tree, but turned upside-down. It is an Abstract Data Type (ADT) for the hierarchical storage of information.
A tree consists of nodes. The first node is called the root of a tree. Every other node in the tree, except the root is known as an element, and each element has a parent and zero or more children elements:
- node A as the Root Node
- node C as the Parent Element of node E
- node F and G are the Children Elements of node E
- all nodes except node A are Elements
Another type of node is the Leaf Node. A leaf node is a node that has No children at all, and is also called an external node. The Leaf Nodes of the above tree are nodes D, F and G because they have no children.
Vice versa, a node is also called an internal node if it has 1 or more children. So above we have the internal nodes of A, B, C and E.
A common example of when a tree like this is used, is something that you use everyday – your file browser 😀 and your Family tree 😉
- If a node u is the parent node of a node v, then the node v is a child node of the node u. Two children of the same parent are called Siblings.
So an example is shown above. The node E is a parent node of F, so F is a child node of E. F and G are children nodes for the same parent node E, so F and G are known as Siblings.
A Binary Tree is an ordered tree in which each node has at most 2 children. A Binary Tree is proper if each internal node has 2 children.
The Binary Tree above is an example of a proper binary tree where each internal node has exactly 2 or 0 children.
Another thing to note is the order in which the numbers have been placed into the tree. The first node contains the number 7. After this, any more numbers that have to be placed into the tree must go in a certain order. If the next number is greater than the current node, go to the child node on the right, else if the next number is less than the current node, go to the child no on the left.
So if we have an empty tree and the list of numbers [7, 5, 9, 6], we get the number 7 first, we have:
After this, the next number is 5. Now 5<7 so we compare 5 to the child on the left of 7. Since there isn’t one, 5 gets inserted here:
Next we have the number 9. Now 9>7 so we compare 9 to the child on the right of 7. There isn’t one so insert 9 here:
Finally we have the number 6. Now 6<7 so compare 6 to the child on the left of 7. On the left we have a number 5. Since 6>5 we then compare 6 to the child on the right of 5. there isn’t one so insert 6 here: