Trees

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 3 - ⇑ Programming Concepts ⇑

← Graphs Trees Tree traversal algorithms for a binary tree →

Trees - A tree is a connected undirected graph with no cycles.


Connected means that every node is connected to at least one other node. Undirected means there is no direction associated with an edge, i.e. lines are used, not arrows. A cycle is a circuit (a succession of edges that start and end at the same vertex) in which all the edges are different and all the vertices visited are different (apart from the start and end vertex).

Tree graph

A rooted tree is a tree in which one vertex has been designed as the root and every edge is directed away from the root.

Binary tree.svg

Exercise: Unordered Binary Trees

For the following tree note the root, leaves and the left sub tree

CPT BinaryTree NumberEx1.svg

Answer :

  • Root = 5
  • Left subtree = 2, 1, 4, 3
  • Leafs = 1, 3, 7, 9
Exercise: Ordered Binary Trees

Create a binary tree for the following data input:

5, 2, 6, 8, 4, 1, 9, 7, 3

Answer :

Sorted tree

Create a binary tree for the following major city input:

Monaco, Paris, Vatican, Rome, Norwich, Lewisham, New York, Partington

Answer :

sorted major global cities. This tree is very right heavy and if you continue Computer Science to University level you would be asked to find ways of balancing trees

Create a binary tree for the following list of animals:

Elephant, Cat, Dog, Hippo, Giraffe, Lion, Bear

Answer :