DataStructures Series — 10
N.B. This article would make more sense if you read previous articles in this series.
In case you missed last week on the data-structures series here.
We discussed the Circular Linked List data structure, a type of Linked List and we wrote some pseudocode to implement some of its operations.
This week, we would be discussing a different ADT called the TREE.
The TREE
A tree is a data structure made up of nodes (or vertices) connected by edges without having any cycle. All Images below are not trees because you can find at least one cycle in all of them.
The tree with no nodes is called the null or empty tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy.
Tree Terminologies:
- Root: The top node in the tree
- Child: A node directly connected to another node above it
- Parent: A node connected to other node(s) below it
- Siblings: A group of node with the same parent
- Leaf: A node with no children
- Degree: The number of children of a given node, A leaf has a zero degree
- Edge: The connection between one node and another
- Path: A sequence of nodes and edges connecting a node and another node
- Level: The level of a node is defined as 1 + the number of edges between the node and the root
- Height of a node: The height of a node is the number of edges on the longest path between the node and the leaf.
- Height of a tree: The height of a tree is the height of its root node.
- Depth of a node: The depth of a node is the number of edges from the tree’s root node to the node.
A Tree Diagram showing some of the terminologies
Tree Main Operations:
- Insertion
- Deletion
- Traversal
- Searching
There are numerous types of trees and we would discussing some of them, write some pseudocode to implement their operations and highlight some of their applications as well.
Next week, we would be discussing the Binary Tree.
REFERENCES:
