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