Question

Write algorithm and program that accepts any tree as input and converts it into binary tree

Answer 1

PROCEDURE CONVERT
[Given a forest of trees, it is required to convert this forest into an equivalent binary tree with a list head (HEAD)].

1. [Initialize]

HEAD <-- NODE
LPTR(HEAD) <-- NULL
RPTR(HEAD) <-- HEAD
LEVEL[1] <-- 0
LOCATION TOP <-- 1.

2. [Process the input]

Repeat thru step 6 while input is there.

3. [Input a node]

Read(LEVEL,INFO).

4. [Create a tree node]

NEW <-- NODE
LPTR(NEW) <-- RPTR(NEW) <-- NULL
DATA(NEW) <-- INFO.

5. [Compare levels]

PRED_LEVEL <-- LEVEL[TOP]
PRED_LOC <-- LOCATION[TOP]
if LEVEL > PRED_LEVEL
then LPTR(PRED_LOC) <-- NEW
else if LEVEL = PRED_LEVEL
RPTR(PRED_LOC) <-- NEW
TOP <-- TOP – 1
else
Repeat while LEVEL != PRED_LEVEL
TOP <-- TOP – 1
PRED_LEVEL <-- LEVEL[TOP]
PRED_LOC <-- LOCATION[TOP]
if PRED_LEVEL <-- LEVEL
then write (“Invalid Input”)
return



RPTR(PRED_LOC) <-- NEW
TOP <-- TOP – 1.

6. [Pushing values in stack]

TOP <-- TOP + 1
LEVEL[TOP] <-- LEVEL
LOCATION[TOP] <-- NEW.

7. [FINISH]
return.

Answer 2

#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 test mirror(). Given a binary   search tree, print out its data elements in    increasing sorted order.*/void inOrder(struct node* node) {  if (node == NULL)     return;     inOrder(node->left);  printf("%d ", node->data);   inOrder(node->right);}    /* Driver <span title="" class="intexthighlight" id="BfiPe" style="line-height: 18.17px;" phasehl="km:en">program</span> 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("\n 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("\n Inorder traversal of the mirror tree is \n");    inOrder(root);     getchar();  return 0;