Page 61 - Data Structures Interactive Book
P. 61
Chapter 7
7.1 Introduction to Trees
Trees are hierarchical data structures that organize elements in a parent-child
relationship. Unlike linear structures such as arrays and linked lists, trees allow branching,
making them ideal for representing hierarchical data like organizational charts, file systems,
and decision processes. A tree consists of nodes connected by edges, with one node
designated as the root. From the root, branches extend to child nodes, forming levels of
hierarchy. This structure enables efficient searching, insertion, and deletion operations in
many applications.
7.1.1 Definition and Characteristics
A tree is defined as a collection of nodes connected by edges, with the following
characteristics:
• There is exactly one root node.
• Each node may have zero or more child nodes.
• Nodes without children are called leaf nodes.
• Trees are acyclic, meaning there are no loops or cycles.
These characteristics make trees suitable for representing hierarchical relationships
and recursive structures.
7.1.2 Terminology (Root, Node, Edge, Height, Depth)
• Root: The topmost node of the tree.
• Node: An element of the tree containing data.
• Edge: A connection between two nodes.
• Height: The length of the longest path from the root to a leaf.
• Depth: The distance of a node from the root.
Understanding this terminology is essential for analyzing and working with trees.
61
