ET210x: Data Structures & Algorithms
Đào Trung Kiên @ MICA Institute & Dept. of Comm. Eng., SEEE, Hanoi Univ. of Science and Technology
Weeks 13+14: Trees
❑General trees
❑Binary trees
❑Threaded binary trees
❑Binary search trees
❑Depth first & breadth first search
1
ET210x: Data Structures & Algorithms
Đào Trung Kiên @ MICA Institute & Dept. of Comm. Eng., SEEE, Hanoi Univ. of Science and Technology
Trees
Used to represent hierarchical
data
A special form of graph
Minimally connected
No loops, no circuits
Always has 𝑛 − 1 edges for 𝑛
vertices
Usually depicted upside down
2
ET210x: Data Structures & Algorithms
Đào Trung Kiên @ MICA Institute & Dept. of Comm. Eng., SEEE, Hanoi Univ. of Science and Technology
Application examples
Classification
Decision making
Data storage, sorting, searching
Computational methods
3
ET210x: Data Structures & Algorithms
Đào Trung Kiên @ MICA Institute & Dept. of Comm. Eng., SEEE, Hanoi Univ. of Science and Technology
Terminology
4
ET210x: Data Structures & Algorithms
Đào Trung Kiên @ MICA Institute & Dept. of Comm. Eng., SEEE, Hanoi Univ. of Science and Technology
List representation
Each node has a list of zero or more child nodes
(a, [
(b, [(d, []),
(e, [])
]),
(c, [(f, [])
])
])
5
➔(a,[(b,[(d,[]),(e,[])]),(c,[(f,[])])])
