Trees 60-67

6.1 Introduction to Trees

Trees are a fundamental non-linear data structure used in computer science for organizing data in a hierarchical manner. Unlike linear data structures such as arrays, stacks, and queues, trees allow for efficient insertion, deletion, and searching of data. A tree consists of nodes connected by edges, where one node is designated as the root. Each node can have zero or more child nodes, and there are no cycles in a tree. Trees are widely used in various applications such as representing hierarchical data (like file systems), parsing expressions, and implementing search algorithms. The structure of a tree allows for efficient traversal and manipulation of data, making it an essential concept in data structures and algorithms.

• A tree is a non-linear, hierarchical data structure.
• It consists of nodes and edges, with one node as the root.
• Each node can have zero or more children.
• Trees do not contain cycles.
• Used in file systems, databases, and search algorithms.
• Efficient for hierarchical data representation.
• 📌 Tree: A non-linear data structure with nodes connected in a hierarchy.
• 📌 Node: A fundamental part of a tree containing data.
• 📌 Edge: A connection between two nodes.

6.2 Basic Terminology and Properties of Trees

Understanding the terminology and properties of trees is crucial for working with this data structure. Key terms include root, parent, child, sibling, leaf, internal node, and level. The root is the topmost node, while leaves are nodes without children. Internal nodes have at least one child. The height or depth of a tree is the length of the longest path from the root to a leaf. The degree of a node is the number of its children. These properties help in analyzing and implementing tree operations efficiently.

• Root is the topmost node of the tree.
• Leaf nodes have no children.
• Internal nodes have at least one child.
• Level of a node is its distance from the root.
• Height of a tree is the longest path from root to a leaf.
• Degree of a node is the number of its children.
• 📌 Parent: Node with children.
• 📌 Child: Node descending from another node.
• 📌 Sibling: Nodes with the same parent.