csl210_lab2b.h
/**
* Lab assignment 2b
* CSL 210 2021
* Deadline: Sunday Oct 10 11pm.
* Submit the c implementation file for this header file
* Filename should be of format YourEnrollmentNumber_lab2b.c (lower case); e.g., bt20cse999_lab2b.c
*
*
* Compilation error = 0
* Late submission = 0
* Presence of uncommented main function in the submission file = 0
* Cheating/plagiarism = 0
* */
#define EMPTYNODE 0
struct btNode{
short value;
struct btNode* left;
struct btNode* right;
};
typedef struct btNode btNode_t;
/**
* Method to find if a subtree in a binary tree is a BST
*
* For this function there is only one input
* i) rootNode: root of a binary tree
*
* Conditions:
* i) There will exactly 0 or 1 BST subtree in the input binary tree
* ii) The number of nodes in the BST subtree will be greater than 2.
* iii) The BST subtree will be a proper subtree, i.e. it will not contain only internal nodes
*
* Return the root node of the subtree that is a BST. Return EMPTYNODE if no BST is a subtree.
* */
btNode_t* getBSTSubtree(btNode_t* rootNode);
main.c
#include <stdio.h>
#include <stdlib.h>
#include "csl210_lab2b.h"
short countNodes(btNode_t *root)
{
if (EMPTYNODE == root)
{
/* code */
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
short is_Bt_Bst(btNode_t *root)
{
static btNode_t *prev = NULL;
if (root != NULL)
{
/* code */
if (!is_Bt_Bst(root->left))
{
/* code */
return 0;
}
if (prev != NULL && root->value <= prev->value)
{
/* code */
return 0;
}
prev = root;
return is_Bt_Bst(root->right);
}
else
{
return 1;
}
}
btNode_t *getBSTSubtree(btNode_t *rootNode)
{
if (NULL == rootNode || 2 >= countNodes(rootNode))
{
/* code */
return EMPTYNODE;
}
if (is_Bt_Bst(rootNode))
{
/* code */
return rootNode;
}
if (countNodes(rootNode->left) > 2)
{
/* code */
btNode_t *a = getBSTSubtree(rootNode->left);
if (a != EMPTYNODE)
{
/* code */
return a;
}
// return getBSTSubtree(rootNode->left);
}
else if (countNodes(rootNode->right) > 2)
{
/* code */
return getBSTSubtree(rootNode->right);
}
}
btNode_t *create_bstnode(int key)
{
btNode_t *newnode = (btNode_t *)malloc(sizeof(btNode_t));
newnode->value = key;
newnode->left = newnode->right = NULL;
return newnode;
}
btNode_t *bstinsert(btNode_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(btNode_t *root)
{
if (root == EMPTYNODE)
return;
inorder(root->left);
printf("%hi ", root->value);
inorder(root->right);
}
int main()
{
btNode_t *root1 = NULL;
root1 = bstinsert(root1, 100);
bstinsert(root1, 23);
bstinsert(root1, 45);
bstinsert(root1, 67);
bstinsert(root1, 10);
inorder(root1);
printf("\n");
btNode_t *a = getBSTSubtree(root1);
inorder(a);
printf("\n");
//any binary tree;
btNode_t *root = create_bstnode(10);
root->left = create_bstnode(11);
root->left->left = create_bstnode(55);
root->left->right = create_bstnode(7);
root->right = create_bstnode(12);
root->right->left = create_bstnode(9);
root->right->left->right = create_bstnode(10);
root->right->right = create_bstnode(15); //change it to 5 , you will get emptynode as result;
inorder(root);
printf("\n");
btNode_t *b = getBSTSubtree(root);
inorder(b);
return 0;
}
Comments
Post a Comment