Augmenting binary search tree. In Josephus problem we start with a set of intege

Question

Augmenting binary search tree. In Josephus problem we start with a set of integers {1,...,n} and we perform a series of operations of the form DEL (k) which delete the integer with position k in the current sorted order. For example DEL(3), DEL(3), DEL(4) deletes 3, then 4 and then 6. Because we only delete (no insertions) we can use an implicit binary search tree: the squareroot is the largest 2^k such that 2^k lessthanorequalto n, this is a node of rank k; a node m of rank k has two children of rank k - 1; m - 2^k-1 and m + 2^k-1. For each node m we store Present [m], the number of the nodes in its subtree that are present, i.e. not greater than n and not deleted yet. Draw the implicit tree of n = 10 and write what are the values of present [] after DEL(8). Write pseudocode that uses this array to perform FIND (k) which returns number/nodes. This should take time O(log n).

Explanation / Answer

Solution: Please follow these program as shown in below

a)

#include<stdlib.h>

#include<stdio.h>

struct bin_tree {

int data;

struct bin_tree * right, * left;

};

typedef struct bin_tree node;

void insert(node ** tree, int val)

{

    node *temp = NULL;

    if(!(*tree))

    {

        temp = (node *)malloc(sizeof(node));

        temp->left = temp->right = NULL;

        temp->data = val;

        *tree = temp;

        return;

    }

    if(val < (*tree)->data)

    {

        insert(&(*tree)->left, val);

    }

    else if(val > (*tree)->data)

    {

        insert(&(*tree)->right, val);

    }

}

void print_preorder(node * tree)

{

    if (tree)

    {

        printf("%d ",tree->data);

        print_preorder(tree->left);

        print_preorder(tree->right);

    }

}

void print_inorder(node * tree)

{

    if (tree)

    {

        print_inorder(tree->left);

        printf("%d ",tree->data);

        print_inorder(tree->right);

    }

}

void print_postorder(node * tree)

{

    if (tree)

    {

        print_postorder(tree->left);

        print_postorder(tree->right);

        printf("%d ",tree->data);

    }

}

void deltree(node * tree)

{

    if (tree)

    {

        deltree(tree->left);

        deltree(tree->right);

        free(tree);

    }

}

node* search(node ** tree, int val)

{

    if(!(*tree))

    {

        return NULL;

    }

    if(val < (*tree)->data)

    {

        search(&((*tree)->left), val);

    }

    else if(val > (*tree)->data)

    {

        search(&((*tree)->right), val);

    }

    else if(val == (*tree)->data)

    {

        return *tree;

    }

}

void main()

{

    node *root;

    node *tmp;

    //int i;

    root = NULL;

    /* Inserting nodes into tree */

    insert(&root, 1);

    insert(&root, 2);

    insert(&root, 3);

    insert(&root, 4);

    insert(&root, 5);

    insert(&root, 6);

    insert(&root, 7);

    insert(&root, 8);

    insert(&root, 9);

    insert(&root, 10);

    /* Printing nodes of tree */

    printf("Pre Order Display ");

    print_preorder(root);

    printf("In Order Display ");

    print_inorder(root);

    printf("Post Order Display ");

    print_postorder(root);

    /* Search node into tree */

    tmp = search(&root, 8);

    if (tmp)

    {

        printf("Searched node=%d ", tmp->data);

    }

    else

    {

        printf("Data Not found in tree. ");

    }

    /* Deleting all nodes of tree */

    deltree(root);

}

b)

b)#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;

};

/* Function to get the count of leaf nodes in a binary tree*/

unsigned int getLeafCount(struct node* node)

{

if(node == NULL)      

    return 0;

if(node->left == NULL && node->right==NULL)     

    return 1;           

else

    return getLeafCount(node->left)+

           getLeafCount(node->right);     

}

/* 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);

}

/*program to test above functions*/

int main()

{

/*create a tree*/

struct node *root = newNode(1);

root->left        = newNode(2);

root->right       = newNode(3);

root->left->left = newNode(4);

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

  

/*get leaf count of the above created tree*/

printf("Leaf count of the tree is %d", getLeafCount(root));

  getchar();

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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