binary search tree

A binary tree is an abstract data type(ADT) in computer science.

conditions of BST:

  • Every tree has only 1 root(head)
  • each node has 2 children
  • If the node is greater than other, then it will go to the right child.
  • if the node is smaller than other, then it will go to the left child.

Advantage:

low complexity O (log n ) 

Disadvantage:

modifications cost O(log n)


Example:

Traversing Tree

There are 3 different methods to traverse the trees. All 3 methods are recursive.

Inorder:

1. Traverse left child 

2. Visit root

3. Traverse the Right child

Postorder:

1. Visit root

2. Traverse left child

3. Traverse the right child 

Preorder:

1. Traverse left child

2.Traverse right child

3. Visit root

Source Code:

/*
 ============================================================================
 Name        : Bintree.c
 Author      : Gennadiy Shevtsov
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */
#include "Bintree.h"
#include <stdio.h>
#include <stdlib.h>



struct Bintreeitem* addItem(struct Bintreeitem* node,int value){
if(node == NULL){
	node  = (struct Bintreeitem*) calloc(1,sizeof(struct Bintreeitem));
	node->value = value;

}
if(value > node->value){
	node->pRight = addItem(node->pRight, value);
	}
if(value < node->value){
    node->pLeft = addItem(node->pLeft, value);
	}
return node;

}

void printTreeInorder(struct Bintreeitem* node) {

  if (node == NULL) return;


  printTreeInorder(node->pLeft);
  printf(" %d ", node->value);
  printTreeInorder(node->pRight);

}
void printTreePostorder(struct Bintreeitem* node) {
  if (node == NULL) return;


  printTreePostorder(node->pLeft);
  printTreePostorder(node->pRight);
  printf(" %d ", node->value);
}
void printTreePreorder(struct Bintreeitem* node) {
  if (node == NULL) return;


  printTreePreorder(node->pLeft);
  printTreePreorder(node->pRight);
  printf(" %d ", node->value);
}
int main(void) {

struct Bintreeitem* pointer = NULL;
pointer = addItem(pointer,5);
pointer = addItem(pointer,2);
pointer = addItem(pointer,3);
pointer = addItem(pointer,8);
pointer = addItem(pointer,1);

printf("Inorder:   ");
printTreeInorder(pointer);
printf("\n");

printf("Postorder: ");
printTreePostorder(pointer);
printf("\n");

printf("Preorder:  ");
printTreePreorder(pointer);
printf("\n");
	return EXIT_SUCCESS;
}

Header File:

#ifndef BINTREE_H_
#define BINTREE_H_
struct Bintreeitem{
	int value;
	struct Bintreeitem* pRight;
	struct Bintreeitem* pLeft;
};
#endif /* BINTREE_H_ */

Output:

Inorder:    1  2  3  5  8 
Postorder:  1  3  2  8  5 
Preorder:   1  3  2  8  5 

Download Full Source Code:

Download

Leave a Reply

Your email address will not be published. Required fields are marked *