Printable View
Hi Guys, I'm reading my course book and I find Tree is quite similar to graph. it look me like a uni-directional non-circular connected graph. But, still i'm amazed with the thought if tree is a graph then why we need to put more focus on this graph and whole graph chapter separately? is there something that make tree a very important data structure in computer science?
A Tree is just a restricted form of a Graph.
Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.
One thing that is important to point out, Trees aren't a recursive data structure. They can not be implemented as a recursive data structure because of the above restrictions. But any DAG implementation, which are generally not recursive, can also be used. My preferred Tree implementation is a centralized map representation and is non recursive.
Graphs are generally search breath first or depth first. The same applies to Tree.
In simple words, tree does not contain cycles and where as graph can. So when we do search, we should avoid cycles in graphs so that we don't get into infinite loops.
Another aspect is tree will typically have some kind of topological sorting or a property like binary search tree which makes search so fast and easy compared to graphs.
Tree is a special case of graph having no loops, no circuits and no self-loops.