Sunday, May 29, 2011
Tuesday, May 24, 2011
Friday, May 20, 2011
Saturday, May 14, 2011
Q. Create a tree from following traversing sequence of a tree.
Pre-order – 1 2 3 4 5 6 7
In-order – 4 2 5 1 6 3 7
Post-order – 4 5 2 6 7 3 1
Answer: To create a tree form traversing sequence we compare pre-order and in-order or post-order and in-order.
- First take one item form pre-order (1), make it root (in in-order traverse 1st item is always is root)
- Choose 2nd item (2), check this item in in-order traverse where it is; left or right side, make child of root as its position in in-order.
- Now take next item (3), again check its position in in-order traverse, put in tree as its position.
Q. Create a tree from following traversing sequence of a tree.
Pre-order – 1 2 3 4 5 6 7
In-order – 4 2 5 1 6 3 7
Post-order – 4 5 2 6 7 3 1
Answer: To create a tree form traversing sequence we compare pre-order and in-order or post-order and in-order.
- First take one item form pre-order (1), make it root (in in-order traverse 1st item is always is root)
- Choose 2nd item (2), check this item in in-order traverse where it is; left or right side, make child of root as its position in in-order.
- Now take next item (3), again check its position in in-order traverse, put in tree as its position.
Height Balanced Tree (AVL Tree)
Height balanced BST (AVL Tree):
It is a special type of BST that remains balanced tree even if the input to the tree is sorted. Each node in an AVL tree maintain balance factor which is calculated as
BAL = (height of left sub-tree) – (height of right sub-tree)
A node is said balanced if its balanced factor is (0, -1, 1).
BAL Otherwise node is unbalanced.
If a node is become unbalanced, it is made balanced by rotating the unbalanced node in opposite direction of unbalanced.
NB - When the sign of balance factor is negative (-ve) then node to be rotated left and when the sign of balance factor is positive (+ve) then node to be rotated right.
NB – When two consecutive nodes got unbalanced then two rotations is needed and first node form leaf side is rotated first then other.
NB – When two consecutive node’s balance factor has opposite sign then youngest node is rotated first according to its sign and then other.
When two or more consecutive nodes got unbalanced nearest node from leaf node should rotate.
Functions:
leftrotate(struct avltree *t)
{
Struct avltree *r, *temp;
r= t->right;
temp = r->left;
r->left = t;
t->right = temp;
}
rightrotate(struct avltree *t)
{
struct avltree *l , *temp;
L = t->left;
l->right = t;
temp = l->right;
l->right = t;
t->left = temp;
}
Height Balanced Tree (AVL Tree)
Height balanced BST (AVL Tree):
It is a special type of BST that remains balanced tree even if the input to the tree is sorted. Each node in an AVL tree maintain balance factor which is calculated as
BAL = (height of left sub-tree) – (height of right sub-tree)
A node is said balanced if its balanced factor is (0, -1, 1).
BAL Otherwise node is unbalanced.
If a node is become unbalanced, it is made balanced by rotating the unbalanced node in opposite direction of unbalanced.
NB - When the sign of balance factor is negative (-ve) then node to be rotated left and when the sign of balance factor is positive (+ve) then node to be rotated right.
NB – When two consecutive nodes got unbalanced then two rotations is needed and first node form leaf side is rotated first then other.
NB – When two consecutive node’s balance factor has opposite sign then youngest node is rotated first according to its sign and then other.
When two or more consecutive nodes got unbalanced nearest node from leaf node should rotate.
Functions:
leftrotate(struct avltree *t)
{
Struct avltree *r, *temp;
r= t->right;
temp = r->left;
r->left = t;
t->right = temp;
}
rightrotate(struct avltree *t)
{
struct avltree *l , *temp;
L = t->left;
l->right = t;
temp = l->right;
l->right = t;
t->left = temp;
}
Q. Write a program to count non leaf node in a tree?
/* Pass address of root in function argument
count_non_leaft(root);
*/
count_nonleaf(struct bintree *t)
{
int c1=0, c2=0;
if(t!=NULL)
{
if(t->left!=NULL||t->right!=NULL)
c1=1;
c2 = return(count_nonleaf(t->left)+c1);
return (count_nonleaf(t->right)+c2);
}
return 0;
}
Q. Write a program to count non leaf node in a tree?
/* Pass address of root in function argument
count_non_leaft(root);
*/
count_nonleaf(struct bintree *t)
{
int c1=0, c2=0;
if(t!=NULL)
{
if(t->left!=NULL||t->right!=NULL)
c1=1;
c2 = return(count_nonleaf(t->left)+c1);
return (count_nonleaf(t->right)+c2);
}
return 0;
}
Q. Write a program to count leaf node in a tree using recursive function.
/*Pass address of root node in function argument...
count_leaf(root);*/
count_leaf(struct bintree *t)
{
int c1 = 0, c2 = 0;
if(t!=NULL)
{
if(t->left == NULL && t->right == NULL)
c1 = 1;
c2 = retun (count_leaf(t->left)+c1);
return (count_leaf(t->right)+c2);
}
return 0;
}
Q. Write a program to count leaf node in a tree using recursive function.
/*Pass address of root node in function argument...
count_leaf(root);*/
count_leaf(struct bintree *t)
{
int c1 = 0, c2 = 0;
if(t!=NULL)
{
if(t->left == NULL && t->right == NULL)
c1 = 1;
c2 = retun (count_leaf(t->left)+c1);
return (count_leaf(t->right)+c2);
}
return 0;
}
