#include <stdio.h> #include <stdlib.h> #include <stdbool.h> /* A binary tree nod
ID: 3690182 • Letter: #
Question
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/* A binary tree node has data, left child and right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* 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);
}
/* A utility function to insert a new node with given data in BST */
struct node* insert(struct node* node, int data)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(data);
/* Otherwise, recur down the tree */
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
/* A utility function to check whether trees with roots as root1 and
root2 are identical or not */
bool areIdentical(struct node * root1, struct node *root2)
{
/* base cases */
if (root1 == NULL && root2 == NULL)
return true;
if (root1 == NULL || root2 == NULL)
return false;
/* Check if the data of both roots is same and data of left and right
subtrees are also same */
return (root1->data == root2->data && areIdentical(root1->left, root2->left) && areIdentical(root1->right, root2->right) );
}
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{
/* base cases */
if (S == NULL)
return true;
if (T == NULL)
return false;
/* Check the tree with root as current node */
if (areIdentical(T, S))
return true;
/* If the tree with root as current node doesn't match then
try left and right subtrees one by one */
return isSubtree(T->left, S) ||isSubtree(T->right, S);
}
// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
/* Driver program to test above function */
int main()
{
int i,n,m;
int number;
printf("Number of nodes in 1st tree: ");
scanf("%d",&n);
printf("Enter the set of numbers for first tree ");
struct node *T = NULL;
scanf("%d",&number);
T = insert(T, number);
for ( i = 1; i < n; ++i)
{
scanf("%d",&number);
insert(T, number);
}
inorder(T);
printf("Number of nodes in 2nd tree: ");
scanf("%d",&m);
printf("Enter the set of numbers for second tree ");
struct node *S = NULL;
scanf("%d",&number);
S = insert(S, number);
for ( i = 1; i < m; ++i)
{
scanf("%d",&number);
insert(S, number);
}
inorder(S);
if (isSubtree(S, T))
printf("First Tree is a subset of second Tree ");
else
printf("First Tree is a not subset of second Tree ");
return 0;
}
Explanation / Answer
// Binary Search Tree Traversal
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef structBST{
int data;
structBST *lchild,*rchild;
}node;
voidinsert(node *,node *);
voidinorder(node *);
voidpreorder(node *);
voidpostorder(node *);
node *search(node *,int,node **);
voidmain(){
intchoice;
charans='N';
intkey;
node *new_node,*root,*tmp,*parent;
node *get_node();
root=NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do{
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your choice :");
scanf("%d",&choice);
switch(choice){
case1:
do{
new_node=get_node();
printf(" Enter The Element ");
scanf("%d",&new_node->data);
if(root==NULL)/* Tree is not Created */
root=new_node;
else
insert(root,new_node);
printf(" Want To enter More Elements?(y/n)");
ans=getch();
}while(ans=='y');
break;
case2:
printf(" Enter Element to be searched :");
scanf("%d",&key);
tmp=search(root,key,&parent);
printf(" Parent of node %d is %d",tmp->data,parent->data);
break;
case3:
if(root==NULL)
printf("Tree Is Not Created");
else{
printf(" The Inorder display : ");
inorder(root);
printf(" The Preorder display : ");
preorder(root);
printf(" The Postorder display : ");
postorder(root);
}
break;
}
}while(choice!=4);
}
/*
Get new Node
*/
node *get_node(){
node *temp;
temp=(node *)malloc(sizeof(node));
temp->lchild=NULL;
temp->rchild=NULL;
returntemp;
}
/*
This function is for creating a binary search tree
*/
voidinsert(node *root,node *new_node){
if(new_node->data<root->data){
if(root->lchild==NULL)
root->lchild=new_node;
else
insert(root->lchild,new_node);
}
if(new_node->data>root->data){
if(root->rchild==NULL)
root->rchild=new_node;
else
insert(root->rchild,new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root,intkey,node **parent){
node *temp;
temp=root;
while(temp!=NULL){
if(temp->data==key){
printf(" The %d Element is Present",temp->data);
returntemp;
}
*parent=temp;
if(temp->data>key)
temp=temp->lchild;
else
temp=temp->rchild;
}
returnNULL;
}
/*
This function displays the tree in inorder fashion
*/
voidinorder(node *temp){
if(temp!=NULL){
inorder(temp->lchild);
printf("%d",temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
voidpreorder(node *temp){
if(temp!=NULL){
printf("%d",temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
voidpostorder(node *temp){
if(temp!=NULL){
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d",temp->data);
}
}
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
typedef structBST{
int data;
structBST *lchild,*rchild;
}node;
voidinsert(node *,node *);
voidinorder(node *);
voidpreorder(node *);
voidpostorder(node *);
node *search(node *,int,node **);
voidmain(){
intchoice;
charans='N';
intkey;
node *new_node,*root,*tmp,*parent;
node *get_node();
root=NULL;
clrscr();
printf(" Program For Binary Search Tree ");
do{
printf(" 1.Create");
printf(" 2.Search");
printf(" 3.Recursive Traversals");
printf(" 4.Exit");
printf(" Enter your choice :");
scanf("%d",&choice);
switch(choice){
case1:
do{
new_node=get_node();
printf(" Enter The Element ");
scanf("%d",&new_node->data);
if(root==NULL)/* Tree is not Created */
root=new_node;
else
insert(root,new_node);
printf(" Want To enter More Elements?(y/n)");
ans=getch();
}while(ans=='y');
break;
case2:
printf(" Enter Element to be searched :");
scanf("%d",&key);
tmp=search(root,key,&parent);
printf(" Parent of node %d is %d",tmp->data,parent->data);
break;
case3:
if(root==NULL)
printf("Tree Is Not Created");
else{
printf(" The Inorder display : ");
inorder(root);
printf(" The Preorder display : ");
preorder(root);
printf(" The Postorder display : ");
postorder(root);
}
break;
}
}while(choice!=4);
}
/*
Get new Node
*/
node *get_node(){
node *temp;
temp=(node *)malloc(sizeof(node));
temp->lchild=NULL;
temp->rchild=NULL;
returntemp;
}
/*
This function is for creating a binary search tree
*/
voidinsert(node *root,node *new_node){
if(new_node->data<root->data){
if(root->lchild==NULL)
root->lchild=new_node;
else
insert(root->lchild,new_node);
}
if(new_node->data>root->data){
if(root->rchild==NULL)
root->rchild=new_node;
else
insert(root->rchild,new_node);
}
}
/*
This function is for searching the node from
binary Search Tree
*/
node *search(node *root,intkey,node **parent){
node *temp;
temp=root;
while(temp!=NULL){
if(temp->data==key){
printf(" The %d Element is Present",temp->data);
returntemp;
}
*parent=temp;
if(temp->data>key)
temp=temp->lchild;
else
temp=temp->rchild;
}
returnNULL;
}
/*
This function displays the tree in inorder fashion
*/
voidinorder(node *temp){
if(temp!=NULL){
inorder(temp->lchild);
printf("%d",temp->data);
inorder(temp->rchild);
}
}
/*
This function displays the tree in preorder fashion
*/
voidpreorder(node *temp){
if(temp!=NULL){
printf("%d",temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
/*
This function displays the tree in postorder fashion
*/
voidpostorder(node *temp){
if(temp!=NULL){
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d",temp->data);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.