Trees

• Data Structures - Chapter 3: Tree-part1

http://www.youtube.com/watch?v=7Ac2qNITEYQ&feature=channel&list=UL

• Tree (data structure)

In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure with a set of linked nodes.
A tree can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of nodes (the "children"), with the constraints that no node is duplicated.
A tree can be defined abstractly as a whole (globally) as an ordered tree, with a value assigned to each node

Representations

There are many different ways to represent trees; common representations represent the nodes as dynamically allocated records with pointers to their children, their parents, or both, or as items in an array, with relationships between them determined by their positions in the array (e.g., binary heap).

http://en.wikipedia.org/wiki/Tree_(data_structure)

• Trees

we shall extend the use of pointers to define a non-linear structure to model hierarchical relationships, such as a family tree.
In such a tree, we have links moving from an ancestor to a parent, and links moving from the parent to children

A tree is a data structure that is made of nodes and pointers, much like a linked list.
The difference between them lies in how they are organized

The height of a tree is defined to be the length of the longest path from the root to a leaf in that tree ( including the path to root)


Tree Examples
Directory Hierarchies:
In computers, files are stored in directories that form a tree.
The top level directory represents the root.
It has many subdirectories and files

Organization charts:

Biological classifications:
Starting from living being at the root, such a tree can branch off to mammals, birds, marine life etc

Game Trees:
All games which require only mental effort would always have number of possible options at any position of the game.
For each position, there would be number of counter moves.
The repetitive pattern results in what is known a game tree

http://www.cs.ucf.edu/courses/cop3502h.02/trees1.pdf

• Trees have many uses:

representing family genealogies
as the underlying structure in decision-making algorithms
to represent priority queues (a special kind of tree called a heap)
to provide fast access to information in a database (a special kind of tree called a b-tree)
http://pages.cs.wisc.edu/~vernon/cs367/notes/8.TREES.html