A binary search tree is a data structure for maintaining sets of values like int

Question

 A binary search tree is a data structure for maintaining sets of     values like integers, which can be compared using a <= relation.     A binary search tree is either empty, or it consists of a node with     two binary search trees as subtrees. Each node holds an integer     element. Binary search trees satisfy the following invariant:The     elements held in the left subtree of a node are smaller than the     element n at the node, and the elements held in the right subtree     of the node are larger than n.     a. Describe an implementation of binary search trees in terms of        records and pointers.    b. Write a function member to determine if an integer is held at some node        in a binary search tree.    c. Write a function print that prints the elements within a binary        search tree in increasing order. 

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node
{
int data;
struct node *left, *right;
};
struct node *newNode(int y)
{
struct node *T = (struct node *)malloc(sizeof(struct node));
T->data = y;
T->left = T->right = NULL;
return T;
}
void increasingorder(struct node *root)
{
if (root != NULL)
{
increasingorder(root->left);
printf("%d ", root->data);
increasingorder(root->right);
}
}
struct node* insert(struct node* node, int x)
{
if (node == NULL) return newNode(x);
if (x < node->data)
node->left = insert(node->left, x);
else if (x > node->data)
node->right = insert(node->right, x);
return node;
}
int main()
{
/* Let BST
5
/
3 7
/ /
2 4 6 8 */
struct node *root = NULL;
root = insert(root, 5);
insert(root, 3);
insert(root, 2);
insert(root, 4);
insert(root, 7);
insert(root, 6);
insert(root, 8);
increasingorder(root);
return 0;
}

a. in binary search tree implementation first declare a structure which is contain one integer value and two pointer one is left pointer of the tree and another one is right pointer of the tree.

one insertion function ,in this function compare the integer value to search a given key in Bianry Search Tree, we first compare it with root, if the key is present at root, we return root. If key is greater than root’s key, we recur for right subtree of root node. Otherwise we recur for left subtree.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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