In computer science, a tree is a hierarchical data structure that represents a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent. Unlike linear data structures, many trees cannot be represented by relationships between neighboring nodes in a single straight line. Trees are used to represent and organize data in a way that is easy to navigate and search.
Some key terms associated with trees include:
- Node: An entity that contains a key or value and pointers to its child nodes.
- Parent Node: The node which is a predecessor of a node is called the parent node of that node.
- Child Node: The node below a given node connected by its edge downward is called its child node.
- Root: The node at the top of the tree is called the root. There is only one root per tree and one path from the root node to any node.
- Leaf Node: The node which does not have any child node is called the leaf node.
- Subtree: Subtree represents the descendants of a node.
There are different types of trees, including binary trees, general trees, and others. Binary trees are a commonly used type, which constrain the number of children for each parent to at most two. When the order of the children is specified, this data structure corresponds to an ordered tree in graph theory. A value or pointer to other data may be associated with every node in the tree, or sometimes only with the leaf nodes, which have no children nodes.
