Trees in Data Structures and Algorithms

undefined
 
T
r
e
e
s
 
1
 
After
 
 
studying this chapter, the student should be able
to
Define  trees 
,
,
Learn the concepts and principles involved in
   Trees
     Binary trees
 
O
O
b
b
j
j
e
e
c
c
t
t
i
i
v
v
e
e
s
s
 
2
 
D
a
t
a
 
s
t
r
u
c
t
u
r
e
 
?
A
 
d
a
t
a
 
s
t
r
u
c
t
u
r
e
 
i
s
 
a
n
 
a
r
r
a
n
g
e
m
e
n
t
 
o
f
 
d
a
t
a
 
i
n
 
a
 
c
o
m
p
u
t
e
r
'
s
m
e
m
o
r
y
 
s
o
 
a
s
 
t
o
 
b
e
 
u
s
e
d
 
e
f
f
e
c
t
i
v
e
l
y
.
هيكلة البيانات هى طريقة لحفظ البيانات فى زاكرة الحاسب حتى يمكن استخدامها بكفاءة
عالية
There are two types of data structure 
ويوجد نوعان 
 .
1-Linear data structure.
هيكلة بيانات خطية
2- Non linear structure .
هيكلة بيانات غير خطية
How can we decide which data structure  to be used?
-What needs to be stored
-
Cost of operation
-
Memory usage .
-
Ease of implementation .
 
D
A
T
A
 
S
T
R
U
C
R
E
 
3
 
Trees:-
A
 
t
r
e
e
 
i
s
 
a
 
(
p
o
s
s
i
b
l
y
 
n
o
n
-
l
i
n
e
a
r
)
 
d
a
t
a
 
s
t
r
u
c
t
u
r
e
 
m
a
d
e
 
u
p
 
o
f
 
n
o
d
e
s
o
r
 
v
e
r
t
i
c
e
s
 
a
n
d
 
e
d
g
e
s
 
w
i
t
h
o
u
t
 
h
a
v
i
n
g
 
a
n
y
 
c
y
c
l
e
.
 
T
h
e
 
t
r
e
e
 
w
i
t
h
 
n
o
n
o
d
e
s
 
i
s
 
c
a
l
l
e
d
 
t
h
e
 
n
u
l
l
 
o
r
 
e
m
p
t
y
 
t
r
e
e
.
 
A
 
t
r
e
e
 
t
h
a
t
 
i
s
 
n
o
t
 
e
m
p
t
y
c
o
n
s
i
s
t
s
 
o
f
 
a
 
r
o
o
t
 
n
o
d
e
 
a
n
d
 
p
o
t
e
n
t
i
a
l
l
y
 
m
a
n
y
 
l
e
v
e
l
s
 
o
f
 
a
d
d
i
t
i
o
n
a
l
n
o
d
e
s
 
t
h
a
t
 
f
o
r
m
 
a
 
h
i
e
r
a
r
c
h
y
إ
ن
 
ا
ل‍
‍ش‍
‍ج‍
‍ر
ة
 
ه‍
‍ى
 
ع‍
‍ب‍
‍ا
ر
ة
 
ع‍
‍ن
 
ب‍
‍ن‍
‍ي‍
‍ة
 
ا
ل‍
‍ب‍
‍ي‍
‍ا
ن‍
‍ا
ت
 
غ‍
‍ي‍
‍ر
 
خ‍
‍ط‍
‍ي‍
‍ة
 
 
ت‍
‍ت‍
‍ك‍
‍و
ن
 
م‍
‍ن
 
ا
ل‍
‍ع‍
‍ق‍
‍د
 
أ
و
 
ا
ل‍
‍ق‍
‍م‍
‍م
 
و
ا
ل‍
‍ح‍
‍و
ا
ف
 
د
و
ن
و
ج‍
‍و
د
 
أ
ي
 
د
و
ر
ة
.
 
و
ي‍
‍ط‍
‍ل‍
‍ق
 
ع‍
‍ل‍
‍ى
 
ش‍
‍ج‍
‍ر
ة
 
م‍
‍ع
 
ع‍
‍د
م
 
و
ج‍
‍و
د
 
ا
ل‍
‍ع‍
‍ق‍
‍د
 
ش‍
‍ج‍
‍ر
ة
 
ف‍
‍ا
ر
غ‍
‍ة
.
 
ش‍
‍ج‍
‍ر
ة
 
ل‍
‍ي‍
‍س‍
‍ت
 
ف‍
‍ا
ر
غ‍
‍ة
ت‍
‍ت‍
‍ك‍
‍و
ن
 
م‍
‍ن
 
ع‍
‍ق‍
‍د
ة
 
ا
ل‍
‍ج‍
‍ذ
ر
 
و
ر
ب‍
‍م‍
‍ا
 
ع‍
‍د
ة
 
م‍
‍س‍
‍ت‍
‍و
ي‍
‍ا
ت
 
م‍
‍ن
 
ا
ل‍
‍ع‍
‍ق‍
‍د
 
إ
ض‍
‍ا
ف‍
‍ي‍
‍ة
 
ا
ل‍
‍ت‍
‍ي
 
ت‍
‍ش‍
‍ك‍
‍ل
 
ت‍
‍س‍
‍ل‍
‍س‍
‍ل
 
ه‍
‍ر
م‍
‍ي
.
 
T
r
e
e
s
 
 
4
 
Root
 – The topmost node in a tree.
Parent
 – The converse notion of a 
child
.
Siblings
 – Nodes with the same parent.
.
 Descendant
 – a node reachable by repeated proceeding
from
parent to child
سليل - عقدة يمكن الوصول إليها من خلال المتابعة المتكررة من الأم إلى الطفل
Ancestor
 – a node reachable by repeated proceeding from
child to parent.
سلف - عقدة يمكن الوصول إليها من خلال إجراءات متكررة من الطفل إلى الأم
.
.
 
T
r
e
e
s
 
d
e
f
i
n
i
t
i
o
n
s
 
5
 
Leaf
 – a node with no children
أ
و
ر
ا
ق
 
-
 
ع‍
‍ق‍
‍د
ة
 
ل‍
‍ي‍
‍س
 
ل‍
‍د
ي‍
‍ه‍
‍ن
 
أ
ط‍
‍ف‍
‍ا
ل
.
.
Internal node
 – a node with at least one child
ع‍
‍ق‍
‍د
ة
 
ا
ل‍
‍د
ا
خ‍
‍ل‍
‍ي‍
‍ة
 
-
 
ع‍
‍ق‍
‍د
ة
 
م‍
‍ع
 
ط‍
‍ف‍
‍ل
 
و
ا
ح‍
‍د
 
ع‍
‍ل‍
‍ى
 
ا
لأ
ق‍
‍ل
.
.
External node
 – a node with no children
.
ع‍
‍ق‍
‍د
ة
 
ا
لخ‍
‍ا
ر
ج‍
‍ي‍
‍ة
 
-
 
ع‍
‍ق‍
‍د
ة
 
ل‍
‍ي‍
‍س
 
ل‍
‍د
ي‍
‍ه‍
‍ن
 
أ
ط‍
‍ف‍
‍ا
ل
.
.
 Degree
 – number of sub trees of a node
.
د
ر
ج‍
‍ة
 
-
 
ع‍
‍د
د
 
ا
لأ
ش‍
‍ج‍
‍ا
ر
 
د
و
ن
 
ع‍
‍ق‍
‍د
ة
 
T
r
e
e
s
 
d
e
f
i
n
i
t
i
o
n
s
 
6
 
Edge
 – connection between one node to another
الحافة - اتصال بين عقدة إلى أخرى
.
Path
 – a sequence of nodes and edges connecting a
node with a Descendant
م‍
‍س‍
‍ا
ر
 
-
 
س‍
‍ل‍
‍س‍
‍ل‍
‍ة
 
م‍
‍ن
 
ا
ل‍
‍ع‍
‍ق‍
‍د
 
و
ح‍
‍و
ا
ف
 
ر
ب‍
‍ط
 
ع‍
‍ق‍
‍د
ة
 
م‍
‍ع
 
س‍
‍ل‍
‍ي‍
‍ل
.
Level
 – The level of a node is defined by 1 + (the
number of connections between the node and the
root)
ويعرف مستوى عقدة 1 + (عدد الاتصالات بين العقدة والجذر)
.
 
 
T
r
e
e
s
 
d
e
f
i
n
i
t
i
o
n
s
 
7
 
Height of tree
 –The height of a tree is the number of edges on the
longest downward path between the root and a leaf
ا
ر
ت‍
‍ف‍
‍ا
ع
 
ش‍
‍ج‍
‍ر
ة
 
-
T
H
E
 
ا
ر
ت‍
‍ف‍
‍ا
ع
 
ش‍
‍ج‍
‍ر
ة
 
ه‍
‍و
 
ع‍
‍د
د
 
ا
لح‍
‍و
ا
ف
 
ع‍
‍ل‍
‍ى
 
أ
ط‍
‍و
ل
 
م‍
‍س‍
‍ا
ر
 
ن‍
‍ز
و
لي
 
ب‍
‍ين
 
ا
لج‍
‍ذ
ر
و
ا
لأ
و
ر
ا
ق
.
.
.
 Height of node
 –The height of a node is the number of edges on
the longest
downward path between that node and a leaf
ا
ر
ت‍
‍ف‍
‍ا
ع
 
ع‍
‍ق‍
‍د
ة
 
-
T
H
E
 
ا
ر
ت‍
‍ف‍
‍ا
ع
 
ع‍
‍ق‍
‍د
ة
 
ه‍
‍و
 
ع‍
‍د
د
 
ا
لح‍
‍و
ا
ف
 
ع‍
‍ل‍
‍ى
 
أ
ط‍
‍و
ل
 
م‍
‍س‍
‍ا
ر
 
ن‍
‍ز
و
لي
 
ب‍
‍ين
 
ت‍
‍ل‍
‍ك
 
ا
ل‍
‍ع‍
‍ق‍
‍د
ة
 
و
ر
ق‍
‍ة
Depth
 –The depth of a node is the number of edges from the node
to the tree's root node.
 عمق عمق -
THE 
من عقدة هو عدد حواف من عقدة إلى عقدة
جذر الشجرة
Forest
 – A forest is a set of n ≥ 0 disjoint trees
غابة - غابة هي مجموعة من ن ≥ 0 أشجار منفصلة.
.
 
T
r
e
e
s
 
d
e
f
i
n
i
t
i
o
n
s
 
8
 
D
e
f
i
n
i
t
i
o
n
:
 
 
A
 
b
i
n
a
r
y
 
t
r
e
e
 
i
s
 
a
 
f
i
n
i
t
e
 
s
e
t
 
o
f
 
n
o
d
e
s
 
w
h
i
c
h
 
i
s
 
e
i
t
h
e
r
e
m
p
t
y
 
o
r
 
c
o
n
s
i
s
t
s
 
o
f
 
a
 
r
o
o
t
 
a
n
d
 
t
w
o
 
d
i
s
j
o
i
n
t
 
b
i
n
a
r
y
t
r
e
e
s
 
c
a
l
l
e
d
the left sub tree and the right sub tree.
ت‍
‍ع‍
‍ر
ي‍
‍ف
:
 
ش‍
‍ج‍
‍ر
ة
 
ث‍
‍ن‍
‍ا
ئ‍
‍ي‍
‍ة
 
ه‍
‍ي
 
م‍
‍ج‍
‍م‍
‍و
ع‍
‍ة
 
م‍
‍ح‍
‍د
و
د
ة
 
م‍
‍ن
 
ا
ل‍
‍ع‍
‍ق‍
‍د
 
ا
ل‍
‍ت‍
‍ي
 
إ
م‍
‍ا
 
ف‍
‍ا
ر
غ‍
‍ة
 
أ
و
 
ت‍
‍ت‍
‍أ
ل‍
‍ف
م‍
‍ن
 
ج‍
‍ذ
ر
 
و
ا
ث‍
‍ن‍
‍ي‍
‍ن
 
م‍
‍ن
 
ا
لأ
ش‍
‍ج‍
‍ا
ر
 
ا
ل‍
‍ث‍
‍ن‍
‍ا
ئ‍
‍ي‍
‍ة
 
ا
ل‍
‍م‍
‍ن‍
‍ف‍
‍ص‍
‍ل‍
‍ة
 
ت‍
‍د
ع‍
‍ى
 
ا
ل‍
‍ش‍
‍ج‍
‍ر
ة
 
ا
ل‍
‍ف‍
‍ر
ع‍
‍ي‍
‍ة
 
ا
ل‍
‍ي‍
‍س‍
‍ر
ى
و
ا
ل‍
‍ي‍
‍م‍
‍ن‍
‍ى
,
 
B
i
n
a
r
y
 
t
r
e
e
 
9
Slide Note
Embed
Share

In this chapter, you will learn about trees as a data structure, including definitions, types, and key concepts such as nodes, edges, levels, and heights. Trees play a crucial role in organizing data efficiently, and understanding them is essential for mastering algorithms and data structures.

  • Data Structures
  • Algorithms
  • Trees
  • Nodes
  • Hierarchies

Uploaded on Jul 10, 2024 | 3 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Data structure and algorithm 2 Trees 1

  2. Objectives After studying this chapter, the student should be able to Define trees , Learn the concepts and principles involved in Trees Binary trees 2

  3. DATA STRUCRE Data structure ? A data structure is an arrangement of data in a computer's memory so as to be used effectively. There are two types of data structure . 1-Linear data structure. 2- Non linear structure . How can we decide which data structure to be used? -What needs to be stored -Cost of operation -Memory usage . -Ease of implementation . 3

  4. Trees Trees:- A tree is a (possibly non-linear) data structure made up of nodes or vertices and edges without having any cycle. The tree with no nodes is called the null or empty tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy . . . 4

  5. Trees definitions Root The topmost node in a tree. Parent The converse notion of a child. Siblings Nodes with the same parent. . Descendant a node reachable by repeated proceeding from parent to child Ancestor a node reachable by repeated proceeding from child to parent. .. - - 5

  6. Trees definitions Leaf a node with no children . . - Internal node a node with at least one child . . - External node a node with no children . . . - Degree number of sub trees of a node . - 6

  7. Trees definitions Edge connection between one node to another - Path a sequence of nodes and edges connecting a node with a Descendant . Level The level of a node is defined by 1 + (the number of connections between the node and the root) ( + ) . - . 1 7

  8. Trees definitions Height of tree The height of a tree is the number of edges on the longest downward path between the root and a leaf THE - . . . Height of node The height of a node is the number of edges on the longest downward path between that node and a leaf Depth The depth of a node is the number of edges from the node to the tree's root node. - THE Forest A forest is a set of n 0 disjoint trees - 0 . THE - . 8

  9. Binary tree Definition: A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left sub tree and the right sub tree. , : 9

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#