btree.c

btree.c

struct btree_node
{
	struct btree_node * u_left;
	struct btree_node * u_right;
	int32_t             u_data;
};

typedef struct btree_node   btree_node;
typedef struct btree_node   btree;
typedef struct btree_node * btree_forest;

#pragma mark -

btree_node * btree_node_create(int32_t data)
{
	struct btree_node * node = malloc(sizeof(struct btree_node));
	node->u_data             = data;
	node->u_left             = NULL;
	node->u_right            = NULL;
	return node;
}

#pragma mark -

btree * btree_create()
{
	struct btree_node * tree = NULL;
	return tree;
}

void btree_destroy(btree * tree)
{
	if (tree != NULL) {
		if (tree->u_left != NULL) {
			btree_destroy(tree->u_left);
			tree->u_left = NULL;
		}
		if (tree->u_right != NULL) {
			btree_destroy(tree->u_right);
			tree->u_right = NULL;
		}
		free(tree);
		tree = NULL;
	}
}

#pragma mark -

btree * btree_insert(btree * tree, int32_t data)
{
	if (tree == NULL) {
		tree = btree_node_create(data);
	} else {
		if (data <= tree->u_data) {
			tree->u_left  = btree_insert(tree->u_left, data);
		} else {
			tree->u_right = btree_insert(tree->u_right, data);
		}
	}
	return tree;
}

#pragma mark -

size_t btree_size(const btree * tree)
{
	if (tree != NULL) {
		return (btree_size(tree->u_left) + 1 + btree_size(tree->u_right));
	}
	return 0;
}

size_t btree_maxdepth(const btree * tree)
{
	size_t depth_left, depth_right;
	if (tree != NULL) {
		depth_left  = btree_maxdepth(tree->u_left);
		depth_right = btree_maxdepth(tree->u_right);
		if (depth_left > depth_right) {
			return(depth_left + 1);
		}
		return (depth_right + 1);
	}
	return 0;
}

#pragma mark -

int btree_lookupfor(btree * tree, int32_t data)
{
	if (tree != NULL) {
		if (target == tree->u_data) {
			return 1;
		} else if (data < tree->u_data) {
			return(btree_lookupfor(tree->u_left, data));
		}
		return(btree_lookupfor(tree->u_right, data));
	}
	return 0;
}

int32_t btree_minvalue(btree * tree)
{
	struct btree_node * node;
	if (tree != NULL) {
		node = tree;
		while (node->u_left != NULL) {
			node = node->u_left;
		}
		return node->u_data;
	}
	return -1;
}

#pragma mark -

int btree_haspathsum(const btree * tree, int32_t sum)
{
	int32_t sub;
	if (tree != NULL) {
		sub = sum - tree->u_data;
		return (
			   btree_haspathsum(tree->u_left, sub)
			|| btree_haspathsum(tree->u_right, sub)
		);
	}
	return (sum == 0) ? 1 : 0;
}

#pragma mark -

void btree_mirroring(btree * tree)
{
	struct btree_node * node;
	if (tree != NULL) {
		btree_mirroring(tree->u_left);
		btree_mirroring(tree->u_right);

		node          = tree->u_left;
		tree->u_left  = tree->u_right;
		tree->u_right = node;
	}
}

void btree_doubling(btree * tree)
{
	struct btree_node * node;
	if (tree != NULL) {
		btree_doubling(tree->u_left);
		btree_doubling(tree->u_right);

		node                 = tree->u_left;
		tree->u_left         = btree_node_create(tree->u_data);
		tree->u_left->u_left = node;
	}
}

#pragma mark -

int btree_equals(const btree * tree_left, const btree * tree_right)
{
	if (tree_left != NULL && tree_right != NULL) {
		return(
			   tree_left->u_data == tree_right->u_data
			&& btree_equals(tree_left->u_left, tree_right->u_left)
			&& btree_equals(tree_left->u_right, tree_right->u_right) 
		);
	} else if (tree_left == NULL && tree_right == NULL) {
		return 1;
	}
	return 0;
}

#pragma mark -

size_t btree_counttrees(const btree * tree, size_t nkeys)
{
	size_t sum = 1, left, right, root;
	(void)tree;
	if (nkeys > 1) {
		sum = 0;
		for (root = 1;root <= nkeys;root++) {
			left  = btree_counttrees((root - 1));
			right = btree_counttrees((nkeys - root));
			sum += (left * right);
		}
	}
	return sum;
}

#pragma mark -

int btree_isbstwithinrange(const btree * tree, int32_t min_value, int32_t max_value)
{
	if (tree != NULL) {
		if (tree->u_data < min_value || tree->u_data > max_value) {
			return 0;
		}
		return (
			   btree_isbstwithinrange(tree->u_left, min_value, tree->u_data)
			&& btree_isbstwithinrange(tree->u_right, (tree->u_data + 1), max_value) 
		);
	}
	return 1;
}

int btree_isbst(const btree * tree)
{ return btree_isbstwithinrange(tree, INT_MIN, INT_MAX); }

#pragma mark -

void btree_show(const btree * tree)
{
	if (tree ! NULL) {
		btreePrintTree(tree->u_left);
		fprintf(stderr, "%d ", tree->u_data);
		btree_show(tree->u_right);
	}
}

void btree_showpostorder(const btree * tree)
{
	if (tree ! NULL) {
		btree_show(tree->u_left);
		btree_show(tree->u_right);
		fprintf(stderr, "%d ", tree->u_data);
	}
}

void btree_showleafpath(const btree * tree, int32_t * path, size_t npath)
{
	size_t i;
	(void)tree);
	for (i = 0; i < npath;i++) {
		fprintf(stderr, "%d ", path[i]);
	}
	fprintf(stderr, "\n");
}

void btree_showpaths(const btree * tree, int32_t * path, int npath)
{
	if (tree ! NULL) {
		path[npath] = tree->u_data;
		++npath;
		if (tree->u_left == NULL && tree->u_right == NULL) {
			btree_showleafpath(path, npath);
		} else {
			btree_showpaths(tree->u_left, path, npath);
			btree_showpaths(tree->u_right, path, npath);
		}
	}
}

void btree_showallpaths(const btree * tree)
{
	int32_t path[2048];
	btree_showpaths(tree, path, 0);
}

#pragma mark -
#pragma mark -

btree_forest * btree_forest_create(size_t n)
{
	struct btree ** forest = malloc(sizeof(struct btree *) * n);
	for (i = 0; i < n; i++) {
		forest[i] = NULL;
	}
	return forest;
}

void btree_forest_destroy(btree_forest * forest, size_t n)
{
	size_t i;
	if (forest != NULL) {
		for (i = 0; i < n; i++) {
			if (forest[i] != NULL) {
				btree_destroy(forest[i]);
				forest[i] = NULL;
			}
		}
		free(forest);
		forest = NULL;
	}
}

#pragma mark -

btree_forest * btree_forest_insert(btree_forest * forest, size_t n, int32_t data)
{
	size_t i;
	if (forest != NULL) {
		for (i = 0; i < n; i++) {
			btree_insert(forest[i], data);
		}
	}
	return forest;
}

btree * btree_forest_treeat(btree_forest * forest, size_t n, size_t index)
{
	if (forest != NULL && (index >= 0 && index < n)) {
		return forest[index];
	}
	return NULL;
}

/* EOF */

@maxencejded

Some of those functions need to be add into my project my_struct 🥇