If you want to know about ADT, please have a look at What is Abstract Date Type?
I recommend you to revisit Linear and Non Linear ADT before start to read further.Tree
Tree is non linear data structure which organizes data in hierarchical structure.
With linear data structures(like Linked List), you traverse from one end of the structure to the other, visiting every element in the structure no more than once. With non-linear data structures(Tree) there may be any number of routes through the structure. That is, at any element you might have a choice of one or more possible routes.
Parts of Tree
Top Node in a Tree.
Every tree must have root node.
In any tree, there must be only one root node. We never have multiple root nodes in a tree.
Connecting link between any two nodes.
In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges.
Node which has branch from it to any other node is called as parent node.
Node which has child / children.
Node which is predecessor of any node.
Child
Node which is descendant of any node.In a tree, all the nodes except root are child nodes.
Siblings
Nodes which are belong to same Parent.
Leaf
The node which does not have a child.
Internal Nodes
Node which has at least one child is called as INTERNAL Node.
Degree
Total number of children of a node.
Level
Root node is said to be at Level 0 and the children of root node are at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on...
Path
Sequence of Nodes and Edges from one node to another node is called as PATH between that two Node.
Length of a Path
Total number of nodes in that path.
Height
Total number of edges from leaf node to a particular node in the longest path is called as HEIGHT of that Node.
Height of the tree
Height of the root node is height of the tree.
Depth
Total number of edges from root node to a particular node is called as DEPTH of that Node.
Depth of the tree
Total number of edges from root node to a leaf node in the longest path is said to be Depth of the tree.
Sub Tree
Each child from a node forms a sub tree recursively.
No comments:
Post a Comment