TREE : A tree is a non linear data structure . Each object of a tree starts with a trunk or root and extends into several branches . Each branch may extend into other branches until finally terminated by a leaf .
Examples of Tree :
- Tree can be viewed as lineage of a person that is referred to as the family tree .
- Organizational chart of a company .
In computer applications , a tree is an hierarchical collection of finite elements . Each element is called a node .
Terms related to tree structure
- Root Node : The unique node in the tree that has no parent node is called the root node or root of the tree . It represents the beginning of the tree .
- Parent Node : The node, which generates links for other nodes , is known as the parent node . The parent node is always above its child nodes .
- Child Node : The node that is directly connected to a parent node is called the child node .
- Subtree : The child node of the root node that has its own child nodes is called the subtree .
- Terminal Nodes : The node having no successor or cjild is called the terminal node .
- Siblings: The nodes having a common parent are called siblings . These are children of the same parent node .
- Depth of Node: Each node has a unique path connecting it to the root . The depth of a node is the total number of nodes between the node and the root , including the root itself . The depth of root node is 0 .
- Hieght of tree : The maximum depth among all of the nodes of a tree is called the height of tree .
- Empty Tree : A tree that has no node is called empty Tree . Its height is -1 .
- Degree of Node : The number of children of a node is called degree of the node .
Types of Tree :
- Singleton Tree : The tree whose root us its only node is called the singleton .
- Full Tree : A tree is called the full tree if all its internal nodes have the same degree and all the leaves are at the same level .
- Binary Tree : A binary tree is a hierarchical collection of a finite number of nodes in which each node can have a maximum of two children . A binary tree may be empty or non empty but a general tree cannot be empty . One child is on theleft side and other is on the right side of the tree or subtree .
- Full binary tree : A binary tree is said to be full binary tree when 1. Its all leaves are at same level . 2. Every node has two children I.e left child and right child .
- Extended Binary Tree (2_Tree) : A binary tree in which each node has either no child or two children is called an extended binary tree .
- Complete Binary Tree: A binary tree is said to be a complete binary tree of height H if
- All nodes at level H_2 and above have two children each .
- A node at level H_1 has one child , it is a left child and all left siblings of the node have two children each .
- Binary Search Tree : A binary tree in which the left child node of a tree or subtree has lesser value than its root node but right child node has greater (or equal) value than its root node is called binary search tree (BST) .