苗火 Nicholas

[Data structures]Binary search tree

2019-7-5 萧 写技术

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

typedef struct _BinaryTree{
	int key;
	struct _BinaryTree *left;
	struct _BinaryTree *right;
}BinaryTree;

int searchBST(BinaryTree *T, int key, BinaryTree *f, BinaryTree **p)
{
	if(T == NULL){
		*p = f;
		return 0;
	}
	if(T->key == key){
		*p = T;
		return 1;
	}		
	if(key < T->key){
		return searchBST(T->left, key, T, p);
	}else{
		return searchBST(T->right, key, T, p);
	}
}

int insertBST(BinaryTree **T, int key)
{
	BinaryTree *p;
	BinaryTree *s;
	if( 0 == searchBST(*T, key, NULL, &p) ){
		s = malloc(sizeof(BinaryTree));
		s->key = key;
		s->left = s->right = NULL;
		if(p == NULL){
			*T = s;
		}else{
			if(s->key < p->key){
				p->left = s;
			}else{
				p->right = s;
			}
		}
		return 1;
	}else{
		return 0;
	}
}

int delete(BinaryTree **p)
{
	BinaryTree *q;
	BinaryTree *s;
	if(NULL == (*p)->right){
		q = *p;
		*p = (*p)->left;
		free(q);
	}else if(NULL == (*p)->left){
		q = *p;
		*p = (*p)->right;
		free(q);
	}else{
		q = *p;
		s = (*p)->left;	
		while(s->right != NULL){
			s = s->right;
		}
		s->right = (*p)->right;
		(*p) = (*p)->left;
		free(q);
	}
}

int deleteBST(BinaryTree **T, int key)
{
	if(*T == NULL){
		return 0;
	}
	if((*T)->key == key){
		return delete(T);
	}else if( key < (*T)->key ){
		return deleteBST( &(*T)->left, key);
	}else{
		return deleteBST( &(*T)->right, key);
	}
}

void printTree(BinaryTree *T){
	if(T == NULL){
		return;
	}
	printf(" %d", T->key );
	printf("(");
	if(T->left != NULL){
		printTree(T->left);
	}
	printf(",");
	if(T->right != NULL){
		printTree(T->right);
	}
	printf(")");
}

void main()
{
	int seq[] = { 0,  45, 24, 53, 45, 12, 24, 90}; 
	int n = sizeof(seq)/sizeof(int);
	int i;
	BinaryTree *T = NULL;

	printf("Original data:\n");
	for (i=0; i<n; i++) {
		printf("%d\t", seq[i]);
	}	
	printf("\n");

	printf("Insert binary search tree:\n");
	for(i=1;i<n;i++){
		insertBST(&T, seq[i]);
	}
	printf("\n");

	printf("Print the tree:\n");
	printTree(T);
	printf("\n");

	printf("Delete node:\n");
	deleteBST(&T, 45);
	printf("Print the tree:\n");
	printTree(T);
	printf("\n");
}

标签: Data Structures data_structures