Fundamentals of Computer Programming with C# HTML version

Chapter 17. Trees
and Graphs
In This Chapter
In this chapter we will discuss tree data structures, like trees and graphs.
The abilities of these data structures are really important for the modern
programming. Each of this data structures is used for building a model of
real life problems, which are efficiently solved using this model. We will
explain what tree data structures are and will review their main advantages
and disadvantages. We will present example implementations and problems
showing their practical usage. We will focus on binary trees, binary search
trees and self-balancing binary search tree. We will explain what graph
is, the types of graphs, how to represent a graph in the memory (graph
implementation) and where graphs are used in our life and in the computer
technologies. We will see where in .NET Framework self-balancing binary
search trees are implemented and how to use them.
Tree Data Structures
Very often we have to describe a group of real life objects, which have such
relation to one another that we cannot use linear data structures for their
description. In this chapter, we will give examples of such branched
structures. We will explain their properties and the real life problems, which
inspired their creation and further development.
A tree-like data structure or branched data structure consists of set of
elements (nodes) which could be linked to other elements, sometimes
hierarchically, sometimes not. Trees represent hierarchies, while graphs
represent more general relations such as the map of city.
Trees are very often used in programming, because they naturally represent
all kind of object hierarchies from our surroundings. Let’s give an example,
before we explain the trees’ terminology.
Example – Hierarchy of the Participants in a Project
We have a team, responsible for the development of certain software project.
The participants in it have manager-subordinates relations. Our team
consists of 9 teammates: