Thread: Find maximum subtree in the given BST such that it has no duplicates

  1. #1
    Registered User
    Join Date
    Jun 2019
    Posts
    1

    Find maximum subtree in the given BST such that it has no duplicates

    I insert new vertices in the tree as follows: left <root <= right. By the "maximum sub-tree" I mean that which is the highest.

    My program works as follows:


    1. Traversing tree using BFS start by visiting the root

    2. Examine the subtree in each visited vertex to see if it contains duplicates, as follows:

    a) check if the right son is not the same as the father

    b) if not, check next left sons

    3. If it contains, enqueue its children for traversal.

    4. If not, enter the new subtree in the list

    5. Find the subtree in the list which is the highest.

    The function that checks if the tree has duplicates works correctly. However, I have a problem with the operations on the list. E.g. function print (which prints the list) doesn't work, so I believe I'm not creating the list properly.

    Code:
    typedef struct vertex {
        int klucz;
        struct vertex *left;
        struct vertex *right;
    } vertex, *pvertex;
    
    typedef struct NondupeSubtree {
        struct vertex *root;
        struct NondupeSubtree *next;
    } NondupeSubtree, *pNondupeSubtree;
    
    int AnyDupes_temp(pvertex v,int k);
    
    int AnyDupes(pvertex t){
    
        if(t==NULL)
            return 0;
        int k = t->klucz;
        pvertex v = t->right;
    
        if(AnyDupes_temp(v,k))
            return 1;
    }
    
    int AnyDupes_temp(pvertex v,int k){
    
        if (v==NULL)  
            return 0;
        if (v->klucz == k)
            return 1;
        if(v->klucz > k)
            return AnyDupes_temp(v->left,k);  
    }
    
    int AnyDupes_total(pvertex root)
    {
        int rear, front;
        pvertex *queue = createQueue(&front, &rear);
        pvertex temp_vertex = root;
    
    
        while (temp_vertex)
        {
            if(AnyDupes(temp_vertex))
                return 1;
            // Enqueue left child
            if (temp_vertex->left)
                enQueue(queue, &rear, temp_vertex->left);
    
            // Enqueue right child
            if (temp_vertex->right)
                enQueue(queue, &rear, temp_vertex->right);
    
            temp_vertex = deQueue(queue, &front);
        }
    }
    
    /* Print all the elements in the linked list */
    void print(pNondupeSubtree head) {
      pNondupeSubtree current_node = head;
      while(current_node){
        printf("%d ", current_node->root->klucz);
        current_node = current_node->next;
      }
    }
    
    /* Add a new node to the top of a list */
    pNondupeSubtree insert_top(pvertex t, pNondupeSubtree head) {
      pNondupeSubtree new_node;
      new_node = (pNondupeSubtree ) malloc(sizeof(NondupeSubtree));
      new_node->root = t;
      new_node->next= head;
      head = new_node;
      return head;
    }
    
    pvertex MaxHeightTree(pNondupeSubtree head)
    {
      pNondupeSubtree p, pmax;
      pmax = head;
      if(head)
        for(p = head->next; p; p = p->next)
          if(Height(p->root) > Height(pmax->root))
            pmax = p;
      return pmax->root;
    }
    
    pvertex Function(pvertex t, pNondupeSubtree pq)
    {
        int rear, front;
        pvertex *queue = createQueue(&front, &rear);
        pvertex temp_vertex = t;
    
    
        while (temp_vertex){
            if(!AnyDupes(temp_vertex)){
    
                pq->next = insert_top(temp_vertex, pq);
                pq=pq->next;
                temp_vertex = deQueue(queue, &front);
            }
            else{
                if (temp_vertex->left)
                    enQueue(queue, &rear, temp_vertex->left);
    
                if (temp_vertex->right)
                    enQueue(queue, &rear, temp_vertex->right);
    
                /*Dequeue vertex and make it temp_vertex*/
                temp_vertex = deQueue(queue, &front);
            }
        }
         MaxHeightTree(pq);
    }
    
    int main()
    {
      pNondupeSubtree head;
      head = (pNondupeSubtree)malloc(sizeof(NondupeSubtree));
      pvertex t = NULL;
    
        DisplayTree(Funkcja(t, head));
        return 0;
    }
    Last edited by stanislaw; 06-15-2019 at 12:42 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to find duplicates in array of structures?
    By oceans in forum C Programming
    Replies: 3
    Last Post: 07-21-2014, 01:05 PM
  2. Binary File-how do you find duplicates?
    By wacky_jay in forum C Programming
    Replies: 6
    Last Post: 10-06-2012, 06:19 AM
  3. C Programming: Find maximum and minimun.
    By TamaraKM in forum C Programming
    Replies: 1
    Last Post: 03-07-2012, 07:52 PM
  4. Find Maximum!
    By alireza beygi in forum C Programming
    Replies: 2
    Last Post: 01-06-2012, 05:41 PM
  5. Best way to find maximum number
    By mutombo in forum C Programming
    Replies: 3
    Last Post: 02-27-2009, 04:36 AM

Tags for this Thread