Multiple binary search tree-CodePudding

I need to create multiple trees in order to compare their shape and calculate how many different shapes of trees I got (identical forms will be counted as one form).

Input will be:

trees (how many trees need to be(from 1 to 50) layers (how many nodes will be in 1 tree (from 1 to 20)

values (values in every tree (from 1 to 1000000))

Input with images:

There must be five trees with three nodes in each.

The first two trees are the same shape, the others are different.

Output: 4

Example of input:

2 2
1 2 
2 1

So there must be two trees with two nodes in each.

Answer is 2 because there can be 2 different forms of trees

Another example of input:

6 7
7 6 3 5 4 2 1 
1 3 2 4 7 5 6 
4 7 1 2 5 3 6 
5 1 6 7 2 4 3 
1 3 2 5 6 4 7 
6 7 1 5 4 2 3

Answer: 6

I was able to create one tree with the structure, but I can't figure out how to create several and how to compare their shapes

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

struct node {
    int item;
    struct node* left;
    struct node* right;
};

struct node *create_node(int item){  //create one node without childrens
    struct node* result = malloc(sizeof(struct node));
    if (result != NULL){
        result->left = NULL;
        result->right = NULL;
        result->item = item;
    }
    return result;
}
void printtabs(int numtabs){ //for levels when trees is printing
    for(int i = 0; i < numtabs; i  ){
        printf("\t");
    }
}

void printtree_rec(struct node *root,int level){ //for a simple tree view 
    if(root == NULL){
        printtabs(level);
        printf("---empty---\n");
        return;
    }
    printtabs(level);
    printf("value = %d\n", root->item);
    printtabs(level);
    printf("left\n");

    printtree_rec(root->left, level 1);
    printtabs(level);
    printf("right\n");

    printtree_rec(root->right,level 1);

    printtabs(level);
    printf("done\n");
}
void printtree(struct node *root){
    printtree_rec(root, 0);
}

bool insertnumber(struct node **rootptr, int item){ //add a number to the tree
    struct node *root = *rootptr;
    if(root == NULL){
        (*rootptr) = create_node(item);
        return true;
    }
    if(item == root->item){
        return false;
    }
    if( item < root->item){ //if less than the root then to the left
        return insertnumber(&(root->left),item);
    }else{                  //if more then to the right
        return insertnumber(&(root->right),item);
    }
    
}
void fast_input(int* int_input) //for fast reading from input
{
    *int_input=0;
     char next_char=0;
        while( next_char < '0' || next_char > '9' ){ // Skip non-digits
            next_char = getchar();
            }
            while( next_char >= '0' && next_char <= '9' )
            {
                (*int_input) = ((*int_input)<<1)   ((*int_input)<<3)   next_char - '0';
                next_char = getchar();
            }
            
}

int main(){
    clock_t tStart = clock();
    struct node *root = NULL;
    int trees;
    int layers;

    fast_input(&trees);
    fast_input(&layers);
    int item;

    for(int x = 0; x < layers; x  ){
        fast_input(&item);
        insertnumber(&root, item);
    }
    
    printtree(root);
    printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC); //need to be less than 5 sec
}

Maybe I don't need multiple trees. Maybe I'll create one tree, write values to it, then somehow "save" its shape, clear it, and then write the next tree to it.

What would be the best way to do it?

CodePudding user response：

Pseudo-code (too long for a comment):

bool SameShape(node* tree1, node* tree2)
{
  if (isNull(tree1))
    if isNull(tree2))
      return true;
    else
      return false;
  else
    if (!isNull(tree2))
      return false;
  if (isNull(tree1->left) != isNull(tree2->left))
    return false;
  if (isNull(tree1->right) != isNull(tree2->right))
    return false;
  bool same = true;
  if (!isNull(tree1->left))
    same = SameShape(tree1->left, tree2->left);
  if (same && !isNull(tree1-right)
    same = SameShape(tree1-right, tree2->right);
  return same;
}

}

CodePudding user response：

For the compare function :

bool IdenticalTreeShape(struct node *tree1, struct node *tree2)
{
    if (!tree1 && !tree2) {
        return true;
    }
    if (  (!tree1)
        ||(!tree2)
        ||(!IdenticalTreeShape(tree1->left, tree2->left)
        ||(!IdenticalTreeShape(tree1->right, tree2->right) ) {
        return false;
    }
    
    return true;
}

Now, you need to retain every uniq shape you found in order to see if a new proposition would be uniq or not. You can do it in many way.

For example :

Have an array arrayUniq of the number of tree that you will input. Have an integer nbUniq set to 0.

Input and create your tree in arrayUniq[nbUniq]

Compare all tree shape from "0" to "nbUniq - 1" against arrayUniq[nbUniq]. If none tree are identical, increase nbUniq.

Done :)