C-8.33 Two ordered trees T and T are said to be isomorphic if one of the followi

Question

C-8.33

Two ordered trees T and T are said to be isomorphic if one of the followingholds:

• Both T and T are empty.

• Both T and T consist of a single node

• The roots of T and T have the same number k 1 of subtrees, and the i th such subtree of T is isomorphic to the i th such subtree of T for i = 1 ,..., k .

Design an algorithm that tests whether two given ordered trees are isomorphic.What is the running time of your algorithm?

C-7.44

Describe a method for performing a card shufe of a list of 2 n elements, byconverting it into two lists. A card shufe is a permutation where a list L is cutinto two lists, L 1 and L 2 , where L 1 is the rst half of L and L 2 is the second half of L , and then these two lists are merged into one by taking the rst element in L 1 , then the rst element in L 2 , followed by the second element in L 1 , the secondelement in L 2 , and so on.

Explanation / Answer

Isomorphic tree Check program:-

#include <iostream>

using namespace std;

/* A binary tree node has data, pointer to left and right children */

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

/* Given a binary tree, print its nodes in reverse level order */

bool isIsomorphic(node* n1, node *n2)

{

// Both roots are NULL, trees isomorphic by definition

if (n1 == NULL && n2 == NULL)

    return true;

// Exactly one of the n1 and n2 is NULL, trees not isomorphic

if (n1 == NULL || n2 == NULL)

    return false;

if (n1->data != n2->data)

    return false;

// There are two possible cases for n1 and n2 to be isomorphic

// Case 1: The subtrees rooted at these nodes have NOT been "Flipped".

// Both of these subtrees have to be isomorphic, hence the &&

// Case 2: The subtrees rooted at these nodes have been "Flipped"

return

(isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))||

(isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left));

}

/* Helper function that allocates a new node with the

   given data and NULL left and right pointers. */

node* newNode(int data)

{

    node* temp = new node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return (temp);

}

/* Driver program to test above functions*/

int main()

{ // Insert the same data in the nodes of both trees ao that the output comes yes. you can also create

// empty tree or tree with single node only as per your requirement.

struct node *n1 = newNode(1);

    n1->left        = newNode(2);

    n1->right       = newNode(3);

    n1->left->left = newNode(4); // T' tree nodes values.

    n1->left->right = newNode(5);

    n1->right->left = newNode(6);

    n1->left->right->left = newNode(7);

    n1->left->right->right = newNode(8);

    struct node *n2 = newNode(1);

    n2->left         = newNode(3);

    n2->right        = newNode(2);

    n2->right->left   = newNode(4); //T'' tree nodes values.

    n2->right->right   = newNode(5);

    n2->left->right   = newNode(6);

    n2->right->right->left = newNode(8);

    n2->right->right->right = newNode(7);

    if (isIsomorphic(n1, n2) == true)

       cout << "Yes";

    else

      cout << "No";

    return 0;

}

The  time complexity is O(m + n) where m and n are number of nodes in given trees as the program/algoritm involves the traversal of both the trees.

List merge program:-

// C Program to shuffle a given array

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// function to split & shuffle and add
void shuffle( int arr[], int n )
{
   int arr1[n/2];
   int arr2[n/2];
   int mergearr[n];
   for (int i =0;i<n/2;i++)
   {
       arr1[i]=arr[i];
   }
   for (int j =(n/2);j<n;j++)
   {
       arr2[j]=arr[j];
   }
   // printing L1
   for (int k = 0;k<n/2;k++)
   {
       printf("%d",arr1[k]);
   }
   printf(" ");
   // printing L2
   for (int z =(n/2);z<n;z++)
   {
       printf("%d",arr2[z]);
   }
   printf(" ");
  
   for(int x=0;x<n;x+2)
   {
   mergearr[x]=arr1[x];
   }
   for(int x=1;x<n;x+2)
   {
   mergearr[x]=arr2[x];
   }
  
   // printing merged list
   for (int p =0;p<n;p++)
   {
       printf("%d",mergearr[p]);
   }
   printf(" ---");
}

// Driver program to test above function.
int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
   int n = sizeof(arr)/ sizeof(arr[0]);
   shuffle(arr, n);
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.