A tree is a connected, undirected graph with no cycles.
• This means that it is possible to travel from any vertex in the tree to any other vertex by following the edges of the tree, but there is no path that starts and ends at the same vertex and follows only distinct edges.
• The tree consisting of a single vertex with no edges is called the trivial tree or the degenerate tree.
→ Properties of Trees:
- There is only one path between each pair of vertices of a tree.
- A tree T with n vertices has n-1 edges.
- In any tree G, there are at least two pendant vertices
- A forest G with n vertices has n-k edges, where k is the number of components of G.
→ Tree Terminologies:
• Node: Each data item in a tree is called a node. It is the basic structure in a tree.
• Root: The root is the top data item (node) in a tree. It has no parent nodes.
• Degree of a node: The degree of a node is the number of child nodes that it has.
• Degree of a tree: The degree of a tree is the maximum degree of any node in the tree.
• Terminal node(s): A terminal node is a node that has no child nodes.
• Non-terminal node(s): A non-terminal node is a node that has at least one child node.
• Siblings: Two nodes are siblings if they have the same parent node.
• Level: The level of a node is the number of edges from the root node to that node.
• Edge: An edge is a connection between two nodes in a tree.
• Path: A path is a sequence of nodes and edges that connects two nodes in a tree.
• Depth: The depth of a node is the length of the longest path from the root node to that node.
• Forest: A forest is a set of two or more disjoint trees.
→ Rooted Trees:
A rooted tree is a tree in which one vertex is designated as the root.
• They are often used to represent hierarchical data structures, such as file systems, family trees, and organization charts. They can also be used to represent search algorithms, such as binary search trees.
