Take the height-balanced tree code, and replace the key field by a field int lea

Question

Take the height-balanced tree code, and replace the key field by a field int leaves. That field should contain the number of leaves below the node, so n->leaves = 1 if n is a leaf, and n->leaves =n->left->leaves + n->right->leaves else. The leaves field must be updated after an insertion or deletion for all nodes on the path from the root to the changed leaf, and after a rotation for the changed nodes.

Replace the find function by

object t *find by number(tree node t *tree, int k);
which returns the object stored in the k-th leaf from left (start counting with the leftmost leaf as 1);

CODE:

#include

#include

#define BLOCKSIZE 256

typedef int object_t;

typedef int key_t;

typedef struct tr_n_t { key_t key;

struct tr_n_t *left;

struct tr_n_t *right;

int height;

} tree_node_t;

tree_node_t *currentblock = NULL;

int size_left;

tree_node_t *free_list = NULL;

tree_node_t *get_node()

{ tree_node_t *tmp;

if( free_list != NULL )

{ tmp = free_list;

   free_list = free_list -> left;

}

else

{ if( currentblock == NULL || size_left == 0)

   { currentblock =

(tree_node_t *) malloc( BLOCKSIZE * sizeof(tree_node_t) );

size_left = BLOCKSIZE;

   }

   tmp = currentblock++;

   size_left -= 1;

}

return( tmp );

}

void return_node(tree_node_t *node)

{ node->left = free_list;

   free_list = node;

}

tree_node_t *create_tree(void)

{ tree_node_t *tmp_node;

   tmp_node = get_node();

   tmp_node->left = NULL;

   return( tmp_node );

}

object_t *find(tree_node_t *tree, key_t query_key)

{ tree_node_t *tmp_node;

   if( tree->left == NULL )

   return(NULL);

   else

   { tmp_node = tree;

while( tmp_node->right != NULL )

{ if( query_key < tmp_node->key )

   tmp_node = tmp_node->left;

else

   tmp_node = tmp_node->right;

}

if( tmp_node->key == query_key )

   return( (object_t *) tmp_node->left );

else

   return( NULL );

   }

}

Explanation / Answer

2)this is second method of height based tree

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

};

/* Compute the "maxDepth" of a tree -- the number of

    nodes along the longest path from the root node

    down to the farthest leaf node.*/

int maxDepth(struct node* node)

{

   if (node==NULL)

       return 0;

   else

   {

       /* compute the depth of each subtree */

       int lDepth = maxDepth(node->left);

       int rDepth = maxDepth(node->right);

       /* use the larger one */

       if (lDepth > rDepth)

           return(lDepth+1);

       else return(rDepth+1);

   }

}

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

}

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

    printf("Hight of tree is %d", maxDepth(root));

    getchar();

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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