Method to convert a BST to Quad Tree.....
csl210_lab2a.h
/**
* Lab assignment 2a
* CSL 210 2021
* Deadline: Sunday Oct 10 11pm.
* Submit the c implementation file for this header file
* Filename should be of format YourEnrollmentNumber_lab2a.c (lower case); e.g., bt20cse999_lab2a.c
*
*
* Compilation error = 0
* Late submission = 0
* Presence of uncommented main function in the submission file = 0
* Cheating/plagiarism = 0
* */
#define EMPTYNODE 0
struct bstNode{
short value;
struct bstNode* left;
struct bstNode* right;
};
typedef struct bstNode bstNode_t;
struct quadNode{
short value;
struct quadNode* child0; // leftmost
struct quadNode* child1; // next to the leftmost
struct quadNode* child2; // right of child1
struct quadNode* child3; // rightmost
};
typedef struct quadNode quadNode_t;
typedef enum {
INORDER = 0,
PREORDER = 1,
POSTORDER = 2
} traversal_t ;
/**
* Method to convert a BST to Quad Tree
* A Quad tree is an ADT similar to BST
* In a Quad Tree following properties hold
* each node has between 0 to 4 children
* values in the leftmost subtree are lesser than the values in subtree to its right
* and likewise until the rightmost subtree
*
* For this function there are two inputs
* i) rootBST: root of a valid BST
* ii) order: order of traversal, i.e. inorder, preorder or postorder
*
* The output of the traversal order of rootBST will be the sequence of input for creating the quad tree.
*
* Return the root node of the quad tree created by your implementation.
* The output will be compared using inorder traversal of quad tree (implemented by the instructor).
* */
quadNode_t* convertBST2QuadTree(bstNode_t* rootBST, traversal_t order);
main.c
#include <stdio.h>
#include <stdlib.h>
#include "csl210_lab2a.h"
#define SPACE_GAP_LEVEL 10
quadNode_t *createNode_Quad(short data)
{
quadNode_t *node = (quadNode_t *)malloc(sizeof(quadNode_t));
node->value = data;
node->child0 = EMPTYNODE;
node->child1 = EMPTYNODE;
node->child2 = EMPTYNODE;
node->child3 = EMPTYNODE;
return node;
}
quadNode_t *getParentNode_Quad(quadNode_t *node, short val, short *child_num)
{
while (EMPTYNODE != node)
{
if ((val < node->value) && (node->child0 == EMPTYNODE))
{
*child_num = 0;
return node;
}
else if ((val < node->value) && (node->child0 != EMPTYNODE))
{
if (node->child0->value < val < node->value && (node->child1 == EMPTYNODE))
{
/* code */
*child_num = 1;
return node;
}
else if (node->child0->value < val < node->value && (node->child1 != EMPTYNODE))
{
/* code */
node = node->child1;
}
else
{
node = node->child0;
}
}
else if ((val > node->value) && (node->child3 == EMPTYNODE))
{
*child_num = 3;
return node;
}
else if ((val > node->value) && (node->child3 != EMPTYNODE))
{
if (node->child3->value > val > node->value && (node->child2 == EMPTYNODE))
{
/* code */
*child_num = 2;
return node;
}
else if (node->child3->value > val > node->value && (node->child2 != EMPTYNODE))
{
/* code */
node = node->child2;
}
else
{
node = node->child3;
}
}
else
{
return EMPTYNODE;
}
}
return EMPTYNODE;
}
void getInorder(bstNode_t *node, short inorder[], short *index_ptr)
{
if (node == NULL)
return;
/* first recur on left child */
getInorder(node->left, inorder, index_ptr);
inorder[*index_ptr] = node->value;
(*index_ptr)++; // increase index for next entry
/* now recur on right child */
getInorder(node->right, inorder, index_ptr);
}
void getPreorder(bstNode_t *node, short Preorder[], short *index_ptr)
{
if (node == NULL)
return;
/* first recur on left child */
getPreorder(node->left, Preorder, index_ptr);
Preorder[*index_ptr] = node->value;
(*index_ptr)++; // increase index for next entry
/* now recur on right child */
getPreorder(node->right, Preorder, index_ptr);
}
void getPostorder(bstNode_t *node, short Postorder[], short *index_ptr)
{
if (node == NULL)
return;
/* first recur on left child */
getPostorder(node->left, Postorder, index_ptr);
Postorder[*index_ptr] = node->value;
(*index_ptr)++; // increase index for next entry
/* now recur on right child */
getPostorder(node->right, Postorder, index_ptr);
}
short countNodes(bstNode_t *root)
{
if (EMPTYNODE == root)
{
/* code */
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
quadNode_t *convertBST2QuadTree(bstNode_t *rootBST, traversal_t order)
{
if (EMPTYNODE == rootBST)
return EMPTYNODE;
short count=countNodes(rootBST);
short arr[count], sz=0;
if (INORDER == order)
{
/* code */
getInorder(rootBST, arr, &sz);
}
else if (PREORDER == order)
{
/* code */
getPreorder(rootBST, arr, &sz);
}
else
{
/* code */
getPostorder(rootBST, arr, &sz);
}
quadNode_t *ret_quad_root = createNode_Quad(arr[0]);
short od;
for (short i = 1; i < sz; i++)
{
quadNode_t *parent = getParentNode_Quad(ret_quad_root, arr[i], &od);
if (EMPTYNODE == parent)
{
/* code */
continue;
}
quadNode_t *nod_quad = createNode_Quad(arr[i]);
if (0 == od)
{
/* code */
parent->child0 = nod_quad;
}
else if (1 == od)
{
/* code */
parent->child1 = nod_quad;
}
if (2 == od)
{
/* code */
parent->child2 = nod_quad;
}
if (3 == od)
{
/* code */
parent->child3 = nod_quad;
}
}
return ret_quad_root;
}
void print_QuadTree(quadNode_t *root, short space)
{
if (root == NULL)
return;
space += SPACE_GAP_LEVEL;
print_QuadTree(root->child3, space);
print_QuadTree(root->child2, space);
print_QuadTree(root->child1, space);
print_QuadTree(root->child0, space);
printf("\n");
for (int i = SPACE_GAP_LEVEL; i < space; i++)
printf(" ");
printf("%d\n", root->value);
}
bstNode_t *getParentNodeBST(bstNode_t *node, short val)
{
while (EMPTYNODE != node)
{
if ((val > node->value) && (node->right != EMPTYNODE))
node = node->right;
else if ((val > node->value) && (node->right == EMPTYNODE))
return node;
else if ((val < node->value) && (node->left != EMPTYNODE))
node = node->left;
else if ((val < node->value) && (node->left == EMPTYNODE))
return node;
else
return EMPTYNODE;
}
return EMPTYNODE;
}
void insertNodeInBST(bstNode_t *root, bstNode_t *newNode)
{
if (EMPTYNODE == root || EMPTYNODE == newNode)
return;
bstNode_t *parent = getParentNodeBST(root, newNode->value);
if (EMPTYNODE == parent)
return;
if (newNode->value > parent->value)
parent->right = newNode;
if (newNode->value < parent->value)
parent->left = newNode;
}
bstNode_t* createNode(short val)
{
bstNode_t *node = (bstNode_t *)malloc(sizeof(bstNode_t));
node->value = val;
node->left = EMPTYNODE;
node->right = EMPTYNODE;
return node;
}
// int main()
// {
// bstNode_t *root = createNode(92);
// insertNodeInBST(root, createNode(43));
// insertNodeInBST(root, createNode(61));
// insertNodeInBST(root, createNode(31));
// insertNodeInBST(root, createNode(27));
// insertNodeInBST(root, createNode(17));
// insertNodeInBST(root, createNode(7));
// insertNodeInBST(root, createNode(29));
// insertNodeInBST(root, createNode(104));
// insertNodeInBST(root, createNode(99));
// insertNodeInBST(root, createNode(98));
// insertNodeInBST(root, createNode(202));
// insertNodeInBST(root, createNode(82));
// insertNodeInBST(root, createNode(85));
// insertNodeInBST(root, createNode(165));
// insertNodeInBST(root, createNode(51));
// quadNode_t *root_qd=convertBST2QuadTree(root,0);
// print_QuadTree(root_qd,0);
// return 0;
// }
bstNode_t *create_bstnode(int key)
{
bstNode_t *newnode = (bstNode_t *)malloc(sizeof(bstNode_t));
newnode->value = key;
newnode->left = newnode->right = NULL;
return newnode;
}
bstNode_t *bstinsert(bstNode_t *root, short key)
{
if (root == NULL)
{
root = create_bstnode(key);
return root;
}
else if (root->value > key)
root->left = bstinsert(root->left, key);
else
root->right = bstinsert(root->right, key);
return root;
}
void inorder_quad(quadNode_t *root)
{
if (root == EMPTYNODE)
return;
inorder_quad(root->child0);
inorder_quad(root->child1);
printf("%hi ", root->value); //hi is format specifier of short int;
inorder_quad(root->child2);
inorder_quad(root->child3);
}
void inorder(bstNode_t *root)
{
if (root == EMPTYNODE)
return;
inorder(root->left);
printf("%hi ", root->value);
inorder(root->right);
}
void preorder(bstNode_t *root)
{
if (root == EMPTYNODE)
return;
printf("%hi ", root->value);
preorder(root->left);
preorder(root->right);
}
void postorder(bstNode_t *root)
{
if (root == EMPTYNODE)
return;
postorder(root->left);
postorder(root->right);
printf("%hi ", root->value);
}
int main()
{
bstNode_t *root = NULL;
root = bstinsert(root, 75);
bstinsert(root, 24);
bstinsert(root, 250);
bstinsert(root, 19);
bstinsert(root, 52);
bstinsert(root,300);
bstinsert(root,101);
bstinsert(root,12);
bstinsert(root,20);
bstinsert(root,92);
bstinsert(root,120);
bstinsert(root,7);
bstinsert(root,15);
bstinsert(root,22);
// bstinsert(root,7);
inorder(root);
quadNode_t *abc = convertBST2QuadTree(root, 0);
printf("\n");
inorder_quad(abc);
printf("\n");
printf("\n");
printf("\n");
abc = convertBST2QuadTree(root, 1);
preorder(root);
printf("\n");
inorder_quad(abc);
printf("\n");
printf("\n");
printf("\n");
abc = convertBST2QuadTree(root, 2);
postorder(root);
printf("\n");
inorder_quad(abc);
/*sample quadtree;
printf("\n\n");
quadNode_t *abc=create_quadnode(23);
abc->child0=create_quadnode(12);
abc->child1=create_quadnode(14);
abc->child2=create_quadnode(56);
abc->child3=create_quadnode(1945);
inorder_quad(abc);
*/
return 0;
}
Comments
Post a Comment