Algorithms – Trees


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 😛

Trees

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:

treenodes So here we have:

  • 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 😉

 

Definitions

  • 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.

 

Binary Trees

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.

trebin

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:

treebin7

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:

treebin75

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:

treebin759

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:

treebin7569

Advertisements

About Badgerati
Computer Scientist, Games Developer, and DevOps Engineer. Fantasy and Sci-fi book lover, also founder of Cadaeic Studios.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: