The tree and the graph are included in the non-linear data structure category, where the tree offers a very useful way of representing a relationship between the nodes in a hierarchical structure and the graph follows a network model. The tree and the graph are differentiated by the fact that a tree structure must be connected and can never have loops, while in the graph there are no such restrictions.
A non-linear data structure consists of a collection of the elements that are distributed in a plane, which means that there is no such sequence between the elements as it exists in a linear data structure.
|Path||Only one between two vertices.||More than one path is allowed.|
|Reason node||It has exactly one raz node.||The graph does not have a raz node.|
|Loops||Loops are not allowed.||The graph may have loops.|
|Complexity||Less complex||More complex comparatively|
|Crossing Techniques||Pre-order, In-order and Post-order.||Search in breadth and search in depth.|
|Number of edges||n-1 (where n is the number of nodes)||Not defined|
|Type of model||Hierarchical||Net|
A tree It is a finite collection of data elements generally called nodes. As mentioned earlier, a tree is a non-linear data structure that organizes data elements in orderly order. It is used to show a hierarchical structure between the various data elements and organize the data into branches that relate the information. The addition of a new edge in a tree results in a loop or circuit formation.
There are several types of trees, such as a binary tree, a binary search tree, an AVL tree, a binary tree, a B tree, etc. Data compression, file storage, arithmetic expression manipulation and game trees are some of the tree's applications. data structure
- There is a node designated at the top of the tree known as the tree's raz.
- The remaining data elements are divided into disjoint subsets, referred to as their subtree.
- The tree expands in height towards the bottom.
- A tree must be connected, which means there must be a route from one reason to all other nodes.
- It does not contain loops.
- A tree has n-1 edges.
There are several terms associated with trees, such as terminal node, edge, level, grade, depth, forest, etc. Among those terms, some of them are described below.
- Edge – A line that connects two nodes.
- level : A tree is divided into levels so that the raz node is at level 0. Then, its immediate children are at level 1, and their immediate children are at level 2 and so on to the terminal or leaf node .
- Degree : is the number of sub-trees of a node in a given tree.
- Depth : is the maximum level of any node in a given tree and is also known as height .
- Terminal Node: the node of Highest level is terminal node, while other nodes, except terminal and raz node, are known as non-terminal nodes.
A graphic It is also a non-linear mathematical data structure that can represent various types of physical structure. It consists of a group of vertices (or nodes) and a set of edges that connect the two vertices. The vertices in the graph are represented as points or circles and the edges are shown as arcs or line segments. An edge is represented by E (v, w) where v and w are the pairs of vertices. The removal of an edge of a connected circuit or graph creates a subgraph that is a tree.
The graphics are classified into several categories, such as directed, not directed, connected, not connected, simple and multi-graphic. Computer network, transport system, social network graphic, electrical circuits and project planning are some of the applications of the graphic data structure. It is also used in the so-called management technique PERT (evaluation technique and program evaluation) and CPM (critical route method) in which the structure of the graph is analyzed.
Properties of a graphic:
- A vertex in a graph can be connected to any number of other vertices using edges.
- An edge can be bidirected or directed.
- An edge can be weighted.
In the graph we also use several terms such as adjacent vertices, trajectory, cycle, grade, connected graph, complete graph, weighted graph, etc. Let's understand some of these terms.
- Adjacent vertices : A vertex a is adjacent to vertex b if there is an edge (a, b) or (b, a).
- Route : A route from a random vertex w is an adjacent sequence of vertices.
- Cycle : It is a route in which the first and last vertices are equal.
- Degree – It is a series of incident edges in a vrtice.
- Connected graphic : If there is a route from a random vertex to any other vertex, then that graph is known as a connected graph.
Key differences between tree and graphic
- In a tree there is only one route between two vertices, while a graph can have unidirectional and bidirectional routes between the nodes.
- In the tree, there is exactly one raz node, and each child can only have one parent. Unlike, in a graph, there is no concept of the raz node.
- A tree cannot have loops and self-loops, while the graph can have loops and self-loops.
- The graphics are more complicated, since it can have loops and auto-loops. In contrast, trees are simple compared to the graphic.
- The tree is traversed using pre-order techniques, in order and post-order. On the other hand, for the path of the graph, we use BFS (search in amplitude) and DFS (search in depth).
- A tree can have n-1 edges. On the contrary, in the graph, there is no predefined number of edges, and it depends on the graph.
- A tree has a hierarchical structure, while the graph has a network model.
Graph and tree are the non-linear data structure that is used to solve several complex problems. A graph is a group of vertices and edges where an edge connects a pair of vertices, while a tree is considered as a minimally connected graph that must be connected and free of loops.