C言語で二分探索木を書いてみた。

C言語で二分探索木を書いてみた。 所要時間１時間。 あってる？

	#include <stdio.h>
	#include <stdlib.h>
	#include <assert.h>
	typedef struct sNode Node;
	struct sNode {
	int value;
	Node *left;
	Node *right;
	};
	Node *create_node(int value) {
	Node *node = (Node *)malloc(sizeof(Node));
	node->value = value;
	node->left = node->right = NULL;
	return node;
	}
	void delete_node(Node *node) {
	free(node);
	}
	void delete_tree(Node *node) {
	if (!node)
	return;
	delete_tree(node->left);
	delete_tree(node->right);
	delete_node(node);
	}
	Node *search(Node *node, int value) {
	if (node->value == value)
	return node;
	else if (node->value > value)
	return node->left ? search(node->left, value) : NULL;
	else {
	assert(node->value < value);
	return node->right ? search(node->right, value) : NULL;
	}
	}
	void insert(Node *node, int value) {
	if (node->value == value)
	return;
	else if (node->value > value) {
	if (node->left) {
	insert(node->left, value);
	} else {
	Node *new_node = create_node(value);
	node->left = new_node;
	}
	} else if (node->value < value) {
	if (node->right) {
	insert(node->right, value);
	} else {
	Node *new_node = create_node(value);
	node->right = new_node;
	}
	}
	}
	void delete(Node *node, Node *parent, int value) {
	if (node->value == value) {
	if (!node->left && !node->right) {
	(parent->left == node) ? (parent->left = NULL) : (parent->right = NULL);
	delete_node(node);
	return;
	}
	if (!node->left) {
	assert(node->right);
	(parent->left == node) ? (parent->left = node->right) : (parent->right = node->right);
	delete_node(node);
	return;
	}
	if (!node->right) {
	assert(node->left);
	(parent->left == node) ? (parent->left = node->left) : (parent->right = node->left);
	delete_node(node);
	return;
	}
	Node *replace_node = node->left;
	Node *replace_node_parent = node;
	while (replace_node->right) {
	replace_node_parent = replace_node;
	replace_node = replace_node->right;
	}
	node->value = replace_node->value;
	(replace_node_parent->left == replace_node ) ? (replace_node_parent->left = replace_node->left) : (replace_node_parent->right = replace_node->left);
	delete_node(replace_node);
	} else if (node->value > value)
	return node->left ? delete(node->left, node, value) : NULL;
	else {
	assert(node->value < value);
	return node->right ? delete(node->right, node, value) : NULL;
	}
	}
	/* test */
	void display(Node *node) {
	if (node->left) {
	display(node->left);
	}
	printf("%d ", node->value);
	if (node->right) {
	display(node->right);
	}
	}
	int main(void) {
	int data;
	Node *root = create_node(10);
	while (scanf("%d", &data) != EOF) {
	insert(root, data);
	}
	display(root);
	printf("\n");
	delete(root, NULL, 10);
	display(root);
	printf("\n");
	delete_tree(root);
	return 0;
	}

view raw gistfile1.c hosted with ❤ by GitHub