binary-search-tree.c

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

typedef struct Node Node;
struct Node {
	int data;
	Node *l;
	Node *r;
};

Node* createNode(int data) {
	Node *n = (Node*)calloc(1, sizeof(Node));
	n->data =  data;
	n->l = NULL;
	n->r = NULL;
	return n;
}

Node* insert(Node *n, int data) {
	if(!n)
		return createNode(data);

	if (n->data > data)
		n->l = insert(n->l, data);
	else
		n->r = insert(n->r, data);
	return n;
}

Node* search(Node *n, int data) {
	if(!n)
		return NULL;

	if (n->data == data)
	return n;
		else if (n->data > data)
	return search(n->l, data);
		else
		return search(n->r, data);
}

Node* findMin(Node *n) {
	if(!n)
		return NULL;
	if(!n->l)
		return n;
	return findMin(n->l);
}

Node* findMax(Node *n) {
	if(!n)
		return NULL;
	if(!n->r)
		return n;
	return findMax(n->r);
}

int findHt(Node *n) {
	if(!n)
		return -1;

	int l = findHt(n->l);
	int r = findHt(n->r);
	return l > r ? l+1 : r+1;
}

Node* delete(Node*n, int data) {
	if (!n)
		return NULL;

	if (n->data > data)
		n->l = delete(n->l, data);
	else if (n->data < data)
		n->r = delete(n->r, data);
	else if (n->data == data) {
		if (n->l && n->r) {
			Node* m = findMin(n->r);
			n->data = m->data;
			n->r = delete(n->r,m->data);
		} else if(n->l) {
			Node* t = n->l;
			free(n);
			n = t;
		} else if(n->r) {
			Node* t = n->r;
			free(n);
			n = t;
		}
		 else {
			free(n);
			n = NULL;
		}
	}
	return n;
}

typedef struct Queue Queue;
struct Queue {
	Node **data;
	int size;
	int capacity;
	int front;
	int end;
};

Queue* initQueue(int capacity) {
	Queue *q = (Queue*)malloc(sizeof(Queue));
	q->data = (Node**)malloc(sizeof(Node*)*capacity);
	q->capacity = capacity;
	q->size = 0;
	q->front =  -1;
	q->end = -1;
	return q;
}

void enqueue(Queue* q, Node* data) {
	if (q->size != q->capacity) {
		q->end = (q->end + 1) % q->capacity;
		q->data[q->end] = data;
		q->size++;
	}
}

Node* dequeue(Queue* q) {
	if (q->size) {
		q->front = (q->front + 1) % q->capacity;
		q->size--;
		return q->data[q->front];
	}
	return NULL;
}

void levelOrder(Node *n) {
	if(!n)
		return;

	Queue *q = initQueue(100);
	enqueue(q,n);
	while(q->size) {
		Node* n = dequeue (q);
		if (!n)
			continue;
		printf("%d ", n->data);
		enqueue(q, n->l);
		enqueue(q, n->r);
	}
}

int checkBST(Node *n, int min, int max) {
	if(!n)
		return 1;
	return (n->data >= min) && (n->data <= max) &&
		   checkBST(n->l, min, n->data) && checkBST(n->r, n->data, max);
}

Node* inOrderSucc(Node *n, int data) {
	Node* p = NULL;
	while (n != NULL) {
        if (n->data < data)
			n = n->r;
        else if (n->data > data) {
            p = n;
			n = n->l;
		} else {
			if(n->r)
				return findMin(n->r);
			else
				return p;
		}
    }
    return NULL;
}

Node* inOrderSuccRecur(Node *n, int data) {
	static int found = 0;
	if(!n)
		return NULL;

	if (n->data == data) {
		found = 1;
		if(n->r)
			return findMin(n->r);
		else
			return NULL;
	} else if (n->data > data) {
		Node* tmp = inOrderSucc(n->l, data);
		if (found)
			return tmp ? tmp : n;
		return NULL;
	} else
		return inOrderSucc(n->r, data);
}

void preOrder(Node *n) {
	if(!n)
		return;

	printf("%d ", n->data);
	preOrder(n->l);
	preOrder(n->r);
}

void inOrder(Node *n) {
	if(!n)
		return;

	inOrder(n->l);
	printf("%d ", n->data);
	inOrder(n->r);
}

void postOrder(Node *n) {
	if(!n)
		return;

	postOrder(n->l);
	postOrder(n->r);
	printf("%d ", n->data);
}

void padding ( char ch, int n )
{
	int i;

	for ( i = 0; i < n; i++ )
		putchar ( ch );
}

void printTree ( Node *root, int level )
{
	int i;

	if ( root == NULL ) {
		padding ( '\t', level );
		puts ( "~" );
	}
	else {
		printTree ( root->r, level + 1 );
		padding ( '\t', level );
		printf ( "%d\n", root->data);
		printTree ( root->l, level + 1 );
	}
}

int main() {
	int d;
	scanf("%d", &d);
	Node* bst = insert(NULL,d);

	while(1){
		char operation[100];
		scanf("%s", operation);
		if (!strcmp(operation, "i"))
		{
			scanf("%d", &d);
			bst = insert(bst,d);
		}
		else if (!strcmp(operation, "s"))
		{
			scanf("%d", &d);
			printf("%d", search(bst,d)->data);
		}
		else if (!strcmp(operation, "m"))
		{
			printf("%d", findMin(bst)->data);
		}
		else if (!strcmp(operation, "M"))
		{
			printf("%d", findMax(bst)->data);
		}
		else if (!strcmp(operation, "d"))
		{
			scanf("%d", &d);
			delete(bst,d);
		}
		else if (!strcmp(operation, "p"))
		{
			// printf("%d %d %d", bst->data, bst->l->data, bst->r->data);
			printTree(bst, 0);
		}
		else if (!strcmp(operation, "h"))
		{
			// printf("%d %d %d", bst->data, bst->l->data, bst->r->data);
			printf("%d", findHt(bst));
		}
		else if (!strcmp(operation, "c"))
		{
			// printf("%d %d %d", bst->data, bst->l->data, bst->r->data);
			printf("%d", checkBST(bst,-__INT32_MAX__, __INT32_MAX__));
		}
		else if (!strcmp(operation, "t"))
		{
			preOrder(bst);
			printf("\n");
			inOrder(bst);
			printf("\n");
			postOrder(bst);
			printf("\n");
		}
		else if (!strcmp(operation, "sc"))
		{
			scanf("%d", &d);
			Node* x = inOrderSucc(bst,d);
			if(!x)
				printf("No Successor\n");
			else
				printf("%d\n", x->data);
		}
		else if (!strcmp(operation, "lv"))
		{
			levelOrder(bst);
		}
	}
	return 0;
}