Page 199 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures Yadwinder Singh, Lovely Professional University

Notes Unit 12: Introduction to Trees

CONTENTS
Objectives
Introduction

12.1 Concept of Trees
12.2 Binary Tree
12.2.1 Binary Tree Creation

12.2.2 Binary Tree Representation
12.3 Traversal of a Binary Tree
12.3.1 Threaded Binary Tree
12.3.2 Non-recursive Traversal using a Threaded Binary Tree
12.4 Summary

12.5 Keywords
12.6 Review Questions
12.7 Further Readings

Objectives

After studying this unit, you will be able to:
Discuss the concept of trees
Explain Binary Tree and its representation
Discuss traversal of Binary tree

Introduction

All data structures provide a way to organize data. Different structures serve different purposes.
Everyone is familiar with the concept of a family tree. In fact, a nice exercise would be to print
the family tree for an individual whose family history is stored in the data base of that case
study. The family tree is actually embedded within the lists containing the family history. Trees
may be viewed as a special case of lists in which no intertwining or sharing takes place. They are
the basis for structures and operations used in all aspects of programming, from the structure of
programs for compilers, to work in data processing, information retrieval and artificial
intelligence. Trees are ubiquitous; they seem to sprout everywhere—even in the field of computer
science! In this unit, we will discuss the concept of trees and binary trees. We will also discuss the
traversal of binary trees.

12.1 Concept of Trees

Tree is a data structure which allows you to associate a parent-child relationship between various
pieces of data and thus allows us to arrange our records, data and files in a hierarchical fashion.
Assume a Tree representing your family structure. Let say we start with your Grand parent; then
come to your parent and finally, you and your siblings.

192 LOVELY PROFESSIONAL UNIVERSITY