Binary Tree
Showing posts with label Binary Tree. Show all posts
Showing posts with label Binary Tree. Show all posts

Pre Order, Post order, In order Implement Binary Tree using linked list

How to write a C Program to implement Binary Tree using linked list. Display the three.. Search and item from the tree with proper message and traverse the tree in Pre Order, Post order and In order in C Programming Language ?


Solution:



/*
Write a program to implement Binary Tree using linked list. Display the three.. Search and item from
the tree with proper message and traverse the tree in
i) Pre Order
ii)Post order
iii) In order
*/

#include< stdio.h>
#include< conio.h>
#include< alloc.h>
struct bstree
{
int data;
struct bstree *lchild,*rchild;
};/*End of struct bstree*/
typedef struct bstree BST;
BST *root=NULL;
BST *create(BST *,int);
void inorder(BST *);
void preorder(BST *);
void postorder(BST *);
void search(BST *,int);
void main()
{
int ch;
int ele;
while(1)
{
clrscr();
printf("\nPress 1 For Insertion.");
printf("\nPress 2 For Inorder Traversal.");
printf("\nPress 3 For Preorder Traversal.");
printf("\nPress 4 For Postorder Traversal.");
printf("\nPress 5 For Search Item.");
printf("\nPress 6 For Exit.");
printf("\nEnter Your Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter Element: ");
scanf("%d",&ele);
root=create(root,ele);
getch();
break;
case 2:
inorder(root);
getch();
break;
case 3:
preorder(root);
getch();
break;
case 4:
postorder(root);
getch();
break;
case 5:
printf("\nEnter Element To Be Searched: ");
scanf("%d",&ele);
search(root,ele);
getch();
break;
case 6:
exit(0);
break;
default:
printf("\nInvalid Choice... Try Again..");
getch();
}/*End of switch(ch)*/
}/*End of while(1)*/
}/*End of void main()*/
BST *create(BST *node,int x)
{
if(node==NULL)
{
node=(BST *)malloc(sizeof(BST));
node->lchild=NULL;
node->rchild=NULL;
node->data=x;
}/*End of if(node==NULL)*/
else if(xdata)
node->lchild=create(node->lchild,x);
else if(x>=node->data)
node->rchild=create(node->rchild,x);
return node;
}/*End of BST *create(BST *,int)*/
void inorder(BST *node)
{
if(node!=NULL)
{
inorder(node->lchild);
printf("%d ",node->data);
inorder(node->rchild);
}/*End of if(node!=NULL)*/
}/*End of void inorder(BST *)*/
void preorder(BST *node)
{
if(node!=NULL)
{
printf("%d ",node->data);
preorder(node->lchild);
preorder(node->rchild);
}/*End of if(node!=NULL)*/
}/*End of void preorder(BST *node)*/
void postorder(BST *node)
{
if(node!=NULL)
{
postorder(node->lchild);
postorder(node->rchild);
printf("%d ",node->data);
}/*End of if(node!=NULL)*/
}/*End of void postorder(BST *node)*/
void search(BST *node,int num)
{
if(node==NULL)
printf("\nThe Number Is Not Present.");
else if(node->data==num)
printf("\nElement Found.");
else if(node->data>num)
search(node->lchild,num);
else
search(node->rchild,num);
}/*End of void search(BST *node,int num)*/

C Program Unvanquished bot behaviour tree

Unvanquished bot behaviour tree


selector
{
sequence
{
condition alertedToEnemy
selector
{
condition haveWeapon( WP_HBUILD ) && ( !buildingIsDamaged || teamateHasWeapon( WP_HBUILD ) )
{
selector
{
action equip
action flee
}
}
action fight
}
}
selector
{
sequence
{
condition team == TEAM_ALIENS
condition healScore <= 0.25
action heal
}
sequence
{
condition team == TEAM_HUMANS
condition !haveUpgrade( UP_MEDKIT )
condition healScore <= 0.25
action heal
}
}
condition team == TEAM_ALIENS
{
action evolve
}
sequence
{
condition team == TEAM_HUMANS
condition !teamateHasWeapon( WP_HBUILD )
condition buildingIsDamaged
decorator timer( 50000 )
{
selector
{
condition !haveWeapon( WP_HBUILD )
{
action buy( WP_HBUILD )
}
condition haveWeapon( WP_HBUILD )
{
action repair
}
}
}
}
condition team == TEAM_HUMANS
{
action equip
}
condition baseRushScore > 0.5
{
action rush
}
action roam
}

BST Tree in C

BST Tree in C BST Tree in C, creation of binary search tree in c, binary search tree deletion program in c, program to delete a node from binary search tree in c, binary tree insertion, binary search tree c code, insertion into binary tree, binary search tree using c, program on binary search tree using c

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

struct BSTree{
int key;
struct BSTree *left;
struct BSTree *right;
struct BSTree *parent; 
};
typedef struct BSTree node;

void add(node **root, int key){     
if((*root)==NULL){
(*root)=(node*)malloc(sizeof(node));
        (*root)->key=key;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->parent=NULL;
}
else{
if(key<(*root)->key){
add(&(*root)->left, key);
(*root)->left->parent=*root;
}
else if (key>(*root)->key){   
add(&(*root)->right, key);
(*root)->right->parent=*root;
}
    }
}

void delete(node **root, int key){
    if(*root){
        if(key < (*root)->key)
delete(&(*root)->left,key);
    else if (key > (*root)->key)
delete(&(*root)->right, key);
    else{
            node *del = *root;
            if(del->left==NULL){
if(del->right) 
del->right->parent=(*root)->parent;
                *root=del->right;
                free(del);
            }
else if (del->right==NULL){
del->left->parent=(*root)->parent;
                *root=del->left;
                free(del);
        }
else{
                node *x=NULL;
                x=del->left;
                node *y=NULL;
                y=del;
                
                while(x->right!=NULL){
                y=x;
                x=x->right;
                }
                int temp = x->key;
                x->key=del->key;
                del->key=temp;
                
                if(y->key != del->key){
                    y->right=x->left;
if(y->right!=NULL) 
y->right->parent=x->parent;
                }
                else{
                    y->left=x->left;
                    if(y->left!=NULL)
y->left->parent=x->parent;
                }
                free(x);
            }    
        }
    }
}

void showInOrder(node *root){
if(root){
showInOrder(root->left);
printf("%d ", root->key);
showInOrder(root->right);
}
}

node* find(node *root, int key){
if(root==NULL)
return NULL;
if(key>root->key)
return find(root->right, key);
else if(key<root->key)
return find(root->left, key);
else
return root;
}

node* min(node *root){
if(root==NULL)
return NULL;
if(root->left)
return min(root->left);
else
return root;
}

node* max(node *root){
if(root==NULL)
return NULL;
if(root->right)
return max(root->right);
else
return root;
}

node* successor(node *root, int key){
node *succ = NULL;
succ = find(root, key);
if(succ){
if(succ->right){
return min(succ->right);
}
node *temp=NULL;
temp = succ->parent;
while(temp && temp->left != succ){
succ = temp;
temp = temp->parent;
}
return temp;
}
printf("Podano zla liczbe!\n");
}

node* predecessor(node *root, int key){
node *prede = NULL;
prede = find(root, key);
if(prede){
if(prede->left){
return max(prede->left);
}
node *temp=NULL;
temp = prede->parent;
while(temp && temp->right != prede){
prede = temp;
temp = temp->parent;
}
return temp;
}
printf("Podano zla liczbe!\n");
}

int sum(node *root){
if(root==NULL)
return 0;
return root->key + sum(root->left) + sum(root->right);
}

void menu(){
printf("___________________________________DRZEWO BST__________________________________\n");
printf("Co chcesz zrobic?\n");
printf("1. Wyswietl drzewo\n");
printf("2. Dodaj wezel\n");
printf("3. Usun wezel\n");
printf("4. Wyswietl nastepnika\n");
printf("5. Wyswietl poprzednika\n");
printf("6. Wyszukaj wartosc\n");
printf("Aby zakonczyc wcisnij ESCAPE\n\n");
}

int main(){

int znak;
int option;
node *number=NULL;
node *root=NULL;
node *searched=NULL;

do{

menu();
znak = getch();
int x;

switch(znak){
case '1':
printf("Drzewo wyswietlone w kolejnosci In Order:\n");
showInOrder(root);
printf("\n\n");
break;
case '2':
printf("Podaj wartosc jaka chcesz dodac: ");
scanf("%d", &option);
printf("\n");
add(&root, option);
break;
case '3':
printf("Podaj wartosc jaka chcesz usunac: ");
scanf("%d", &option);
printf("\n");
delete(&root, option);
break;
case '4':
printf("Podaj wartosc, dla ktorej chcesz wyswietlic nastepnika: ");
scanf("%d", &option);
printf("\n");
number = successor(root, option);
if(number)
printf("Nastepnik wynosi: %d\n\n", number->key);
else
printf("Nastepnik nie istnieje!\n\n");
break;
case '5':
printf("Podaj wartosc, dla ktorej chcesz wyswietlic poprzednika: ");
scanf("%d", &option);
printf("\n");
number = predecessor(root, option);
if(number)
printf("Poprzednik wynosi: %d\n\n", number->key);
else
printf("Poprzednik nie istnieje!\n\n");
break;
case '6':
printf("Podaj wartosc, ktora chcesz wyszukac: ");
scanf("%d", &option);
printf("\n");
searched = find(root, option);
if(searched)
printf("Podana wartosc istnieje. Jej adres wynosi: %p\n\n", searched);
else
printf("Podana wartosc nie istnieje!\n\n");
break;
case '7':
x=sum(root);
printf("%d\n\n", x);
break;
}
}
while(znak != 27);


return 0;
}

C Program Implement Binary Search Tree And Its Traversals

How to write a c program binary tree and its traversals in C Programming Language ?



https://en.wikipedia.org/wiki/Tree_traversal

Solution:
/* Binary tree and its traversals */

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

struct btree* create(struct btree*, int);
void inorder(struct btree*);
void preorder(struct btree*);
void postorder(struct btree*);
void levelorder(struct btree*);

int l=0,r=0,i;

struct btree
{
int data;
struct btree *lptr, *rptr;
};

int main()
{

struct btree *root;
root=NULL;


int value,b,n;

do
{
printf("\nCase options\n1->Enter elements into btree\n2->Inorder print\n3->Preorder print\n4->Postorder print\n5->Levelorder print\n0->Exit\n");
scanf("%d",&b);

switch(b)
{
case 1: printf("\nHow many elements u want to enter the elements in the btree\n");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("\nEnter the value into the btree\n");
scanf("%d",&value);
root = create(root,value);
}
printf("No. of nodes:\nTo left: %d\nTo Right: %d\nIn Totality: %d\n",l,r, (l+r+1) );
break;

case 2: printf("\n Inorder print\n");
inorder(root);
break;

case 3: printf("\n Pre order print\n");
preorder(root);
break;

case 4: printf("\n Post order print\n");
postorder(root);
break;

case 5: printf("\n Level order print\n");
levelorder(root);
break;

case 0: break;
}
if( b==0)
exit (0);
}
while(b!=0);
}


struct btree* create(struct btree *root, int value)
{
struct btree *temp,*temp1;
struct btree *nn;
if(root == NULL)
{
printf("\nThe newnode is the root node\n");
nn = (struct btree*)malloc(sizeof(struct btree));

nn->data = value;
nn->lptr = NULL;
nn->rptr = NULL;
root=nn;
}

else if (root != NULL)
{
temp = root;

while (temp != NULL)
{
temp1=temp;

if(temp->data >= value)
{
if (temp->data != value)
temp= temp->lptr;
else
{
printf("\nRe-enter a unique value\n");
i--;
break;
}
}

else if(temp->data <= value)
{
if(temp->data != value)
temp= temp->rptr;

else
{
printf("\nRe-enter a unique value\n");
i--;
break;
}
}
}


if(temp1->data >value)
{
temp1->lptr= (struct btree*)malloc (sizeof(struct btree*));
l++;
temp1=temp1->lptr;
temp1->data=value;
temp1->lptr=temp1->rptr=NULL;
}
if(temp1->data <value)
{
temp1->rptr= (struct btree*)malloc (sizeof(struct btree*));
r++;
temp1=temp1->rptr;
temp1->data=value;
temp1->lptr=temp1->rptr=NULL;

}
}

return root;

}


void inorder (struct btree* root)
{
if( root !=NULL)
{
inorder(root->lptr);
printf("%d\n", root->data);
inorder(root->rptr);
}
}

void preorder (struct btree* root)
{
if( root !=NULL)
{
printf("%d\n", root->data);
preorder(root->lptr);
preorder(root->rptr);
}
}

void postorder (struct btree* root)
{
if( root !=NULL)
{
postorder(root->lptr);
postorder(root->rptr);
printf("%d\n", root->data);
}
}

void levelorder (struct btree* root)
{
static struct btree *t1, *t2;
t1=root;

printf("%d\n", root->data);

levelorder(t1->lptr);
printf("%d\n", t1->data);

t2=root;

levelorder(t2->rptr);
printf("%d\n", t2->data);
}
Subscribe to: Posts (Atom)