[go: up one dir, main page]
Scribd
Upload
24 views17 pages

PROGRAM 3.a, B, C

The document discusses three programs related to binary search trees: 1) performing basic operations on a binary search tree, 2) performing different tree traversals, and 3) performing operations on an AVL tree. Algorithms and code are provided for each program. The output is verified for each program.

Uploaded by

PRADEEP
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
24 views17 pages

PROGRAM 3.a, B, C

The document discusses three programs related to binary search trees: 1) performing basic operations on a binary search tree, 2) performing different tree traversals, and 3) performing operations on an AVL tree. Algorithms and code are provided for each program. The output is verified for each program.

Uploaded by

PRADEEP
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 17

Ex.no:3.

a Binary search tree


Date:

AIM:
To write a program to perform the operations of binary search tree.

ALGORITHM:
Step 1.Start the process.

Step 2. Check whether the tree is empty or not.

Step 3. If the tree is empty, search is not possible.

Step 4. Otherwise, first search the root of the tree.

Step 5. If the key does not match with the value in the root, search its subtrees.

Step 6. If the value of the key is less than the root value, search the left
subtree.

Step 7. If the value of the key is greater than the root value, search the right
subtree.

Step 8. If the key is not found in the tree, return unsuccessful search.

Step 9. Stop the process.

CODE:

#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
struct node* newNode(int item)
{
struct node* temp
= (struct node*) malloc( sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
struct node* insert(struct node* node, int key)
{
return node;
}
void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
int main()
{
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
inorder(root);
return 0;
}

Output
20 30 40 50 60 70 80
Descriptio Max 90-100% 80-89% 70-79% 60-59% 50%
n
Algorithm
& coding
Output
Execution
Viva
Total

Result:
The program is executed successfully and output is
verified.
Ex.no:3.b Traversal on binary trees
Date:

AIM:
To write a program to perform traversal operations on binary trees.

ALGORITHM:
Step 1:Startthe process.

Step 2:Create structure method and structure variables.

Step 3:CreateinorderTraversal(), preorderTraversal(),


postorderTraversal() functions.
Step 4:Display the all three Traversal Functions.

Step 5:Stop the process.

CODE:
#include <stdio.h>
#include <stdlib.h>

struct node {
int item;
struct node* left;
struct node* right;
};
void inorderTraversal(struct node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}
void preorderTraversal(struct node* root) {
if (root == NULL) return;
printf("%d ->", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void postorderTraversal(struct node* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}
struct node* createNode(value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}
struct node* insertLeft(struct node* root, int value) {
root->left = createNode(value);
return root->left;
}
struct node* insertRight(struct node* root, int value) {
root->right = createNode(value);
return root->right;
}

int main() {
struct node* root = createNode(1);
insertLeft(root, 2);
insertRight(root, 3);
insertLeft(root->left, 4);
printf("Inorder traversal \n");
inorderTraversal(root);

printf("\nPreorder traversal \n");


preorderTraversal(root);

printf("\nPostorder traversal \n");


postorderTraversal(root);
}
OUTPUT:
Inorder traversal
4 ->2 ->1 ->3 ->
Preorder traversal
1 ->2 ->4 ->3 ->
Postorder traversal
4 ->2 ->3 ->1 ->
Descriptio Max 90-100% 80-89% 70-79% 60-59% 50%
n
Algorithm
& coding
Output
Execution
viva
total
Result:
The program is executed successfully and output is verified.
Ex.no:3.c AVL trees
Date:

AIM:
To write a program to perform operations on AVL trees.

ALGORITHM:
Step 1.Start the process.

Step 2. Check whether the tree is empty or not

Step 3. If the tree is empty, search is not possible

Step 4. Otherwise, first search the root of the tree.

Step 5. If the key does not match with the value in the root, search its
subtrees.

Step 6. If the value of the key is less than the root value, search the left
subtree

Step 7. If the value of the key is greater than the root value, search the
right subtree.

Step 8. If the key is not found in the tree, return unsuccessful search.

Step 9. Stop the process.

CODE:

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};

int getHeight(struct Node *n){


if(n==NULL)
return 0;
return n->height;
}

struct Node *createNode(int key){


struct Node* node = (struct Node *) malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
int max (int a, int b){
return (a>b)?a:b;
}
int getBalanceFactor(struct Node * n){
if(n==NULL){
return 0;
}
return getHeight(n->left) - getHeight(n->right);
}

struct Node* rightRotate(struct Node* y){


struct Node* x = y->left;
struct Node* T2 = x->right;
x->right = y;
y->left = T2;
x->height = max(getHeight(x->right), getHeight(x->left)) + 1;
y->height = max(getHeight(y->right), getHeight(y->left)) + 1;

return x;
}

struct Node* leftRotate(struct Node* x){


struct Node* y = x->right;
struct Node* T2 = y->left;

y->left = x;
x->right = T2;

x->height = max(getHeight(x->right), getHeight(x->left)) + 1;


y->height = max(getHeight(y->right), getHeight(y->left)) + 1;

return y;
}

struct Node *insert(struct Node* node, int key){


if (node == NULL)
return createNode(key);

if (key < node->key)


node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

node->height = 1 + max(getHeight(node->left), getHeight(node-


>right));
int bf = getBalanceFactor(node);

if(bf>1 && key < node->left->key){


return rightRotate(node);
}
if(bf<-1 && key > node->right->key){
return leftRotate(node);
}
if(bf>1 && key > node->left->key){
node->left = leftRotate(node->left);
return rightRotate(node);
}
if(bf<-1 && key < node->right->key){
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}

void preOrder(struct Node *root)


{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main(){
struct Node * root = NULL;
root = insert(root, 100);
root = insert(root, 200);
root = insert(root, 400);
root = insert(root, 500);
root = insert(root, 600);
root = insert(root, 300);
preOrder(root);
return 0;
}

OUTPUT:
400 200 100 300 500 600

Descriptio Max 90-100% 80-89% 70-79% 60-59% 50%


n
Algorithm
& coding
Output
Execution
viva
total
Result:
The program is executed successfully and output is verified.

You might also like