04 - Binary Tree

Well, now you're going to learn about Binary Tree,

Binary Tree is a concept that allows faster searching (than linear), well why are you using Binary Tree when using hash table complexity 1??

Because the binary tree is memory-efficient. It doesn't order more space than what it should have, for example, arr[15] you've already allocate 15 memory when using binary tree it will only have the same memory as the input.

Binary Tree just imagines heaven or hell, heaven is in the sky so it's higher, hell is in the ground so it's lower, there are 4 commands.1 Input, delete, search, and display.

Input

Now when you're going to input imagine earth is the data,

1. Check if the earth is empty or not if it is then plugged the data there.

2. If it does then check whether the earth is higher or lower then the input then implement the data in heaven or hell.

3. Run it through recursive and you have Binary Tree.

Get it? No?...

Example with number:

The input is 50

Now check the data have data or not, since it's the first input so it doesn't have data.

50

. now input 30

since there's data and 50 is less than 30 it will be put on hell.

30 50

now input 40

since 40 is lower than 50 and higher than 30 it will be put on hell then heaven.

30 40 50

now input 20

since 20 is lower than 50 and lower than 30 it will be put on hell then hell

The result will be:

*Reminder all the data is unique so there's no case where the data have the same earth if there's it will not be inputted.

Delete

Now when you're going to delete there's 4 condition

1. There's no earth.

2. There's only hell.

3. There's only heaven.

4. There are heaven and hell.

The concept of delete

1. If there no data in earth then there's no data that suits the input.

2. You want to recursive to find the number itself (lower then go to check hell, higher then check heaven).

3. If the data is found check is there hell or heaven if one of them doesn't exist the just set the earth to heaven or hell if both don't exist just set to NULL.

4. If both exist then go left once then recursive till the final right from the left one. Why ? because it will always be less than the earth. For example, the earth is 1 then what is lower than 1 but also fits the position 0.9 since there's no branch and it will always be lower than heaven.

5. Run it again on deleted earth since the last data it will be deleted.

Search

1. Basically the same with delete just this one shows if there's data or not.

2. If there no data in earth then there's no data that suits the input.

3. You want to recursive to find the number itself (lower then go to check hell, higher then check heaven).

4. Print the data.

Display

Imagine all the data look like a pyramid, there are 3 types of display,

1. Inorder

2. Preorder

3. Postorder

1. Inorder

It will go to the left first then go to the right.

Example the input: 50 30 20 10 70 40 15

The answer will be 10 15 20 30 40 50 70

So from the earth, it will go to the most left, print the left first then go to the right. Example, when you see 30 and 20 it will print 20 30 then the right of 30 which is 40 (so when you read it, it will the answer will always go upward).

2. Preorder

The concept is the same with inorder except this time it will go from top to bottom, by using the same example:

50 30 20 10 15 40 70

3. Postorder

The concept is the same with inorder except this time it will go to the most left but print the most right first then print the most left, by using the same example:

15 10 20 40 30 70 50

Coding in c:

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

struct Data{

int num;

struct Data *left,*right;

};

typedef struct Data Dt;

Dt* newNode(int num){

Dt*node = (Dt*)malloc (sizeof(Dt));

node->num=num;

node->left=NULL;

node->right=NULL;

return node;

}

Dt *insert(Dt* curr,int num){

if(curr==NULL){

return newNode(num);

}

if(num< curr->num){

curr->left=insert(curr->left,num);

}else if(num> curr->num){

curr->right=insert(curr->right,num);

}

return curr;

}

void displayInOrder(Dt *curr){

if(curr!=NULL){

displayInOrder(curr->left);

printf("%d ",curr->num);

displayInOrder(curr->right);

}

}

void displayPreOrder(Dt *curr){

if(curr!=NULL){

printf("%d ",curr->num);

displayPreOrder(curr->left);

displayPreOrder(curr->right);

}

}

void displayPostOrder(Dt *curr){

if(curr!=NULL){

displayPostOrder(curr->left);

displayPostOrder(curr->right);

printf("%d ",curr->num);

}

}

Dt *menuInput(Dt* root){

int num;

do{

system("cls");

printf("Input -1 to exit\n1. In-order\n");

displayInOrder(root);

printf("\n2. Pre-order\n");

displayPreOrder(root);

printf("\n3. Post-order\n");

displayPostOrder(root);

printf("\nInput: ");

scanf("%d",&num);

if(num ==-1){

break;

}

root=insert(root,num);

}while(num!=-1);

printf("\n");

return root;

}

Dt* successor(Dt*curr){

Dt*p;

p=curr->left;

while(p->right=NULL){

p=p->right;

}

return p;

}

Dt* menuDelete(Dt* curr,int num){

if(curr==NULL){

printf("There's no Data\n");

return curr;

}else {

if(num<curr->num){

curr->left=menuDelete(curr->left,num);

}else if(num>curr->num){

curr->right=menuDelete(curr->right,num);

}else{

if(curr->left==NULL||curr->right==NULL){

Dt *temp=NULL;

if(curr->left!=NULL){

temp=curr->left;

}else{

temp=curr->right;

}

if(temp==NULL){ //case 1

temp=curr;

curr=NULL;

}else{ //case 2 3

*curr=*temp;

}

free(temp);

}else { //case 4

Dt *temp=successor(curr);

curr->num=temp->num;

curr->left = menuDelete(curr->left,temp->num);

}

}

}

return curr;

}

void mainMenu(){

Dt *root=NULL;

int choice=0;

do{

printf("1. Add\n2. Delete\n3. Exit\n");

do{

printf("Input: ");

scanf("%d",&choice);

}while(choice<0&&choice>3);

if(choice==1){

root=menuInput(root);

}else if(choice==2){

int num;

system("cls");

printf("Input Number: ");

scanf("%d",&num);

root=menuDelete(root,num);

}

}while(choice!=3);

}

int main(){

mainMenu();

}