Transcript Data structure

MINISTRY OF EDUCATION & HIGHER EDUCATION
COLLEGE OF SCIENCE AND TECHNOLOGY
KHANYOUNIS- PALESTINE
DATA STRUCTURE
Information Technology , 3’rd Semester
Using C#
Lecture 13:
Trees
Presented By: Mahmoud Rafeek Alfarra
Outline
Classification of Data Structures
 The definition of a tree
 Terminology of Tree
 Binary Trees
 Binary Search Tree
 Emank X Mezank !!

Classification of Data Structures
3
Classification
Linear
Hierarchical
Presented & Prepared by: Mahmoud R. Alfarra
The definition of a tree
4

A tree is a set of nodes connected by edges.
An example of a tree is a company’s
organization chart
Presented & Prepared by: Mahmoud R. Alfarra
The definition of a tree
5
The purpose of an organization chart is to communicate
to the viewer the structure of the organization.
root node
internal
nodes
leaf nodes
Presented & Prepared by: Mahmoud R. Alfarra
Terminology of Tree
6
 Tree: A collection of data whose entries have a
hierarchical organization
 Node: An entry in a tree
 Root node: The node at the top
 Terminal or leaf node: A node at the bottom
Presented & Prepared by: Mahmoud R. Alfarra
Terminology of Tree
7
 Parent: The node immediately above a specified node
 Child: A node immediately below a specified node
 Ancestor: Parent, parent of parent, etc.
 Descendent: Child, child of child, etc.
 Siblings: Nodes sharing a common parent
Presented & Prepared by: Mahmoud R. Alfarra
Terminology of Tree
8
 Binary tree: A tree in which every node has at most
two children
 Depth: The number of nodes in longest path from root
to leaf
Presented & Prepared by: Mahmoud R. Alfarra
Terminology of Tree
9
Presented & Prepared by: Mahmoud R. Alfarra
Binary Trees
10
 Tree nodes contain two or more links

Most of other data structures we have discussed only contain one
 In Binary trees
 All nodes contain two links
 None, one, or both of which may be NULL
 The root node is the first node in a tree.
 Each link in the root node refers to a child
 A node with no children is called a leaf node
Presented & Prepared by: Mahmoud R. Alfarra
Binary Trees
11
Allow the head (and the rear) to be moving targets
B
A
D
C
Presented & Prepared by: Mahmoud R. Alfarra
Binary Tree Definitions
12
 Leaf: node that has no left and right children
 Parent: node with at least one child node
 Level of a node: number of branches on the
path from root to node
 Height of a binary tree: number of nodes no
the longest path from root to node
Presented & Prepared by: Mahmoud R. Alfarra
Binary search trees
14
5
10
2
5
10
45
30
5
45
30
2
25
45
2
10
25
30
25
Not a binary
search tree
Binary
search trees
Presented & Prepared by: Mahmoud R. Alfarra
‫!! ‪Emank X Mezank‬‬
‫أعظم أسبـاب النجاة‬
‫استعن ابهلل‬
Next Lecture
Examples
(Implementation of tree and
then Practices )