Thursday 30 July 2015

Trees In Data Structure

What is Tree:
A tree is a non linear data structure. A tree is a way of representing the hierarchical nature of a structure in graphical form.
A tree is a set of nodes that either:is empty or has a designated node, called the root, from
which hierarchically descend zero or more sub trees, which are also trees.



Terminology
  • The Degree of a node is the number of sub trees of the nodes
  • The Node with zero degree or has no children is called leaf or terminal node(E,H,C,I,K,G).
  • A node that has subtrees is the parent of the roots of the subtrees
  • The roots of these subtrees are the children of the node.
  • Children of the same parent are siblings.
  • The ancestors  of a node are all the nodes along the path from the root to the node.
  • Root of tree is the node with no parents. There can be at most one root in a tree(node A in the above example)
  • Children of same parent are called siblings(B,C, D are siblings).
  • The height of a node is the length of the path from that node to deepest node. Height of a tree is the length of a path from root to deepest node in the tree.(Height of tree is 6 in the above example A to M)
  • The depth of a node is the length of the path from root to that node.(depth of F is 3, A-D-F)




 Binary Tree:
     
        A tree is called binary tree if each node has zero child, one child or two children. Empty  tree is also a binary tree.
Example:


Binary Tree Traversal
  1. DFS(Depth First Search): Depth-first traversal (Arkiletian traversal) is easily implemented via a stack
    1. Pre-Order
    2. Post Order
    3. In Order
  2. BFS (Breath First Search) is also known as level order in Tree. breadth-first traversal is easily implemented via a queue
 

Structure of Binary Tree:

public class BinaryTree {
    private int data;
    private BinaryTree left;
    private BinaryTree right;
   
    public BinaryTree() {
    }
    public BinaryTree(int data) {
        this.data=data;
    }
    public Integer getData() {
        return data;
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public BinaryTree getLeft() {
        return left;
    }
    public void setLeft(BinaryTree left) {
        this.left = left;
    }
    public BinaryDataTree getRight() {
        return right;
    }
    public void setRight(BinaryTree right) {
        this.right = right;
    }
   
}







Operations on Binary Tree:
  1. Inserting an element in to a tree.
  2. Deleting an element from a tree.
  3. Search for an element
  4. Traversing a tree             
Auxiliary Operations:
  1. Finding size of a tree
  2. Height of a tree
  3. LCA
  4. Sum of the tree
  5. Mirror Image etc.

Note: Will explain different problem on tree in next couple of articles. Subscribe for it.

No comments:

Post a Comment