Thursday, March 21, 2013

Data Structures - For my Ninth Grader – Part 4

Data Structures - For my Ninth Grader – Part3

Data Structures - For my Ninth Grader – Part 2

Data Structures - For my Ninth Grader – Part 1



Tree: As name suggest, tree data structure resembles to a tree.




Just think of a USA’s geography. For administrative purpose it is divided into states and then into counties and finally into city/towns. It represents a Tree.





In this tree Country: USA is Root Node. Root Node is the parent node which does not have any parent. Each node has only one parent node.

A tree can also be thought of as a Set of Linked Lists.

 



One can do following operations on a tree:

  1. 1.     Visiting all the items
    2.      Visiting nodes of a section of a tree
    3.      Searching for a node
    4.      Adding a new node at a certain position on the tree
    5.      Deleting a node
    6.      Pruning: Removing a whole section of a tree
    7.      Grafting: Adding a whole section to a tree
    8.      Finding the parent for any node
Key terms
 

Node: An element/item in a tree
Root Node: Node at the "top" of a tree - the one from which all operations on the tree commence.
Leaf Node: Node at the "bottom" of a tree - farthest from the root. Leaf nodes have no children.
Parent Node: A node directly above a given node (except Root Node)
Child Node: A node directly below a given node
Complete Tree: Tree in which each leaf is at the same distance from the root.
Height: Number of nodes which must be traveled from the root to reach a leaf of a tree.

Your computer file structure is an very good example of a Tree
 

No comments:

Post a Comment