Trees


Tree:::
      A Tree t is a finite non empty set of elements one of these elements is called root. And the remaining elements are partioned into subtrees of t.

Degree of an element :::
                The no of children the element has.

Degree of the tree:::
                The maximum of degrees of its elements.

Level:::
     The level of the root is 0 and the level of any node is one more than its parent.

Height:::
     The height of a binary tree is the no. of levels in it.

Binary Tree :::
          A Binary tree is a finite set of elements posibbly empty.When binary tree is not empty ,it has a root element  the remaining elements are partitioned in to two binary trees.

Trees                        |         Binary Trees
______________________|_______________________
1.Non empty set.      |     1.Can be empty.
2.Can have any no.   |     2.Maximum two decendents
   of decendents        |

Example of a tree ::

The essential differences between a tree and a binary tree:::

-> A Binary tree can be empty, but a tree can’t.
-> Each element in a binary tree has exactly two subtrees(one or both of     these may be empty).Each element in a tree can have any no. of subtrees.
-> The subtrees of each element in a binary tree are ordered i.e. we     distinguish between left and right subtrees.

Properties of binary tree:::
1) The binary Tree with ‘n’ elements has exactly n-1 edges.
2) A Binary Tree of height ‘h’ ,h>0 has atleast h and at most 2^h-1 elements     in it.
3) The height of a binary tree that contains n(n>=0) elements is at least     equal to ceil( log with base2 (n+1) ) and at most equal to n.

Full Binary Tree:::
          A binary tree of height h that contains exactly 2^h -1 elements is called a full binary tree.

Complete Binary Tree:::
          A Complete Binary Tree is a binary Tree in which all the leaves are at the same level.

A Binary of height h is a complete binary tree if and only if
1) Any node at level less than h-1 has two children.
2) Let i,1<=i<=n ,be the number assigned to an element of a complete     binary tree . The following are true.
    i) If i=1, then this element is the root of the complete binary tree.
       If i>1, then the parent of this element is assigned with number        flore(i/2).
    ii) If 2i>n then this element has no left tree, otherwise , its legt chaild         has been assigned the number 2i.
    iii) If 2i+1 > n , then this element has no left chaild ,otherwise its left          child has been assigned the number 2i+1.

Binary tree traversals :::
            1)Pre order traversal
            2)Post order traversal
            3)In order traversal

-> Pre order traversal :::
            In this type of traversal the root is visited first and then the left     subtree is visited and then right sub tree is visited.

An example program is given in the following link
                       preorder_traversal
-> In order traversal :::
            In this type of traversal the left subtree is visited first and then  the root is visited and then right sub tree is visited.

An example program is given in the following link
                       postorder_traversal
-> In order traversal :::
            In this type of traversal the left sub treeroot is visited first and then the right subtree is visited and then  root is visited.

An example program is given in the following link
                       inorder_traversal

One thought on “Trees”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s