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 Then vou (1) 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 (2) replace the insert function by void insert_by_number(tree-node-t *tree, int k, object.t *new_obj); which inserts new-obj in a new k-th leal, moving all leaves above it one step to the right (without renumbering), and (3) replace the delete function by object.t * delete_by_number (tree_node.t *tree, int k); which deletes (and returns) the object stored in the k-th leaf, moving all leaves above it one step to the left (without renumbering)

Explanation / Answer

ANSWER:

HEIGHT BASE TREE CODE

#include <stdio.h>

#include <stdlib.h>

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

}

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.