- Tree is a hierarchical data structure which stores the information naturally in the form of hierarchy style.
- Tree is a data structure that is similar to our trees in nature which is most powerful and advanced datastructure.
- Trees are well known as a non-linear Data Structure. It doesn’t store data in a linear way.
- It organizes data in a hierarchical way.
- Tree is a collection of entities called node connected by edges.
- Unlike trees in nature, the tree data structure is upside down: the root of the tree is on top.
- A tree consists of nodes and its connections are called edges. The bottom nodes are also named leaf nodes.
- Python doesn't have any built in way to create tree data structture but we can implement using list and other data structure.
-
Database Application.
-
File System in Unix or Linux.
-
Imagine a family tree with all generation relationship: grandparents, parents, children, siblings, etc. We commonly organize it in a hierarchical way.
-
A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero ormore children elements
- Tree reflects structural relationships in the data.
- Tree It provides an efficient insertion and searching operations. Trees are flexible. It allows to move subtrees around with minimum effort.
- Node
- Edge
- Root Node
- Leaf Node
- Parent Node
- Child Node
- Siblings
- Degree
- Height
- Depth
- Level
- Where Node have Zero or more children.
- Each Node contains value and some Links to its child.
- The Connection between two node is called as edge.
- In any Given tree the the connection between two node is called as edge.
- If "N" no of Nodes present in the tree the the count of edges should be "N-1" times.
- Root node is the very first or parent node in tree.
- Normally a tree start with root and then goes up to its crown so root node is the first node of the given tree
- A Node without any children is called leaf node or terminal nod.
- In hierarchy Leaf node Placed at the End of the tree where tree nodes do not have any child
- A Node Which hase a branch from it to any other node such node is called as parent node.
- Predecessor of any node is called parent node.
- A Normal Node which has a child Node is called as parent node.
- A Node which has a link from its parent node is called as child Node
- descendant of any node is called as Child Node
- Any Successor of node is called as Child node.
- The Node which has same parent is called as siblings.
- In simple word Nodes with the same parent are sibling nodes.
Degree Of Node: total number of direct children of that node is called degree of that node.
Degree Of Tree
The degree of the tree is the total number of it's children.
- Every node who has at least one child is called as internal node
- all Non-Leaf Nodes are called as Internal Node.
- We can also call Non-Terminal Node to Internal node.
- The Each Step From Top(Root Node) to Bottom is called as level of the tree
- level of treee count started from 0.
- Root Node is placed at 0th level.
- Total no of edges from root node to specific given node is called the Depth of the node.
- Depth of Root Node is Zero(0)
- Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
- Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
- Height of leaf node is always 0.
