TREES

HOME


Definition of a Tree:

A tree is a set of one or more nodes T such that:
(i).There is a specially designated node called a root
(ii).The remaining nodes are partitioned into n disjointed
set of nodes T1, T2,…,Tn, each of which is a tree.

Degree of a Node of a Tree:
The degree of a node of a tree is the number of subtrees having this node as a root. In other words,the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.

Degree of a Tree:
The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max(degree(node i) for I = 1 to n)

Level of a Node:
We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees.We then define the depth of the tree to be the maximum value of the level of the node of the tree.

Binary tree:
A tree T is finite set of nodes, such that
(i).T is empty(called Empty binary tree),
(ii).T contains specially designed node called the root
of T,and the remaining nodes of T form T1 and T2
which are called as left subtree and right subtree.

Binary Search Tree:
Def:
A Binary Tree is said to be Binary Search Tree, the values in the left subtree should be less than that of root element and the values in the right subtree should be greater than that of root element.


Tree Traversals:
Traversing is nothing but visiting all the nodes of a Tree exactly once.
In-order Traversal:
•visit left sub tree of the Root node using In-order traversal
•visit Root node
•visit right sub tree of the Root node using In-order traversal

Pre-order Traversal:
•visit Root node
•visit left sub tree of the Root node using Pre-order Traversal
•visit right sub tree of the Root node using Pre-order Traversal

Post-order Traversal:
•visit left sub tree of the Root node using Post-order Traversal
•visit right sub tree of the Root node using Post-order Traversal
•visit Root node

HOME

Advertisements

2 Comments »

  1. 1
    RAM Says:

    what is 2-3 tree?

    what are AVL rotations?

  2. 2
    Anil CSE Says:

    Bhanu btrees code ekkada.code vunte pettu.


RSS Feed for this entry

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

%d bloggers like this: