Write an algorithm that accepts a Tree as input and converts it into a Binary Tree and then prints all the leaf nodes that are part of both Tree and Binary Tree
Answers
Answer:
This is done in C :
#include <stdio.h>
#include <stdlib.h>
struct tnode
{
int data;
struct tnode *lchild, *rchild;
};
struct tnode *insert(struct tnode *p,int val)
{
struct tnode *temp1,*temp2;
if(p == NULL)
{
p = (struct tnode *) malloc(sizeof(struct tnode));
/* insert the new node as root node*/
if(p == NULL)
{
printf("Cannot allocate\n");
exit(0);
}
p->data = val;
p->lchild=p->rchild=NULL;
}
else
{
temp1 = p;
/* traverse the tree to get a pointer to that node
whose child will be the newly created node*/
while(temp1 != NULL)
{
temp2 = temp1;
if( temp1 ->data > val)
temp1 = temp1->lchild;
else
temp1 = temp1->rchild;
}
if( temp2->data > val)
{
temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->lchild;
if(temp2 == NULL)
{
printf("Cannot allocate\n");
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
else
{
temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
/*inserts the newly created node as left child*/
temp2 = temp2->rchild;
if(temp2 == NULL)
{
printf("Cannot allocate\n");
exit(0);
}
temp2->data = val;
temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}
/* a function to binary tree in preorder */
void preorder(struct tnode *p)
{
if(p != NULL)
{
printf("%d\t",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
if(p != NULL)
{
inorder(p->lchild);
printf("%d\t",p->data);
inorder(p->rchild);
}
}
/* a function to binary tree in postorder */
void postorder(struct tnode *p)
{
if(p != NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf("%d\t",p->data);
}
}
void main()
{
struct tnode *root = NULL;
int n,x;
clrscr();
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
while(n!=0)
{
printf("Enter the data value\n");
scanf("%d",&x);
root = insert(root,x);
n--;
}
printf("\n**THIS TREE IS BINARY TREE**\n");
printf("\nPREORDER OF TREE : \n");
preorder(root);
printf("\nINORDER OF TREE : \n");
inorder(root);
printf("\nPOSTORDER OF TREE : \n");
postorder(root);
getch();
}
Explanation:
Answer:
/ C program to convert a binary tree
// to its mirror
#include<stdio.h>
#include<stdlib.h>
/* A binary tree node has data, pointer
to left child and a pointer to right child */
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Change a tree so that the roles of the left and
right pointers are swapped at every node.
So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
*/
void mirror(struct Node* node)
{
if (node==NULL)
return;
else
{
struct Node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp
= node->left;
node->left = node->right;
node->right = temp;
}
}
/* Helper function to print Inorder traversal.*/
void inOrder(struct Node* node)
{
if (node == NULL)
return;
inOrder(node->left);
printf("%d ", node->data);
inOrder(node->right);
}
/* Driver program to test mirror() */
int main()
{
struct Node *root = newNode(1);
root->left
= newNode(2);
root->right
= newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/* Print inorder traversal of the input tree */
printf("Inorder traversal of the constructed"
" tree is \n");
inOrder(root);
/* Convert tree to its mirror */
mirror(root);
/* Print inorder traversal of the mirror tree */
printf("\nInorder traversal of the mirror tree"
" is \n");
inOrder(root);
return 0;
}
Output :
Inorder traversal of the constructed tree is
4 2 5 1 3
Inorder traversal of the mirror tree is
3 1 5 2 4
Explanation:
Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.
Method 1 (Recursive)
Algorithm – Mirror(tree):
(1) Call Mirror for left-subtree i.e., Mirror(left-subtree)
(2) Call Mirror for right-subtree i.e., Mirror(right-subtree)
(3) Swap left and right subtrees.
temp = left-subtree
left-subtree = right-subtree
right-subtree = temp