はじめての C
次は 二分木の削除。 できれば キーボードから 入力したいのだが、どうも うまく できないので、ヘッダファイルに 書き込むことに ...
/* b_delete.c */
#include
#include
#include "b_delete.h"struct Node {
int data;
struct Node *left;
struct Node *right;
};
int new_node();
int tree_insert();
void btree_walk();
int tree_remove();
main()
{
int value;
struct Node *root;
root = NULL;
while (fscanf(stdin, "%d", &value) != EOF)
tree_insert(&root, value);
btree_walk(root);
putchar('\n');
printf("remove > %d\n", DELETE);
tree_remove(&root, DELETE);
btree_walk(root);
putchar('\n');
return 0;
}
int new_node(struct Node **node, int value)
{
*node = malloc(sizeof(**node));
if (*node == NULL)
return 0;
(*node)->data = value;
(*node)->left = NULL;
(*node)->right = NULL;
return 1;
}
int tree_insert(struct Node **tree, int value)
{
struct Node **prev, *node;
prev = tree;
node = *tree;
for ( ; ; ) {
if (node == NULL)
return new_node(prev, value);
else if (value > node->data) {
prev = &node->right;
node = node->right;
}
else if (value < node->data) {
prev = &node->left;
node = node->left;
}
else
return 1;
}
}
void btree_walk(struct Node *tree)
{
if (tree == NULL)
return;
btree_walk(tree->left);
printf("%d ", tree->data);
btree_walk(tree->right);
}
int tree_remove(struct Node **tree, int value)
{
struct Node **prev, *node;
struct Node *right, *heir;
prev = tree;
node = *tree;
for ( ; ; ) {
if (node == NULL)
return 0;
else if (value > node->data) {
prev = &node->right;
node = node->right;
}
else if (value < node->data) {
prev = &node->left;
node = node->left;
}
else
break;
}
if (node->right == NULL)
*prev = node->left;
else {
right = node->right;
if (right->left == NULL) {
right->left = node->left;
*prev = right;
}
else {
heir = node->left;
while (heir->left != NULL) {
right = heir;
heir = right->left;
}
right->left = node->right;
heir->left = node->left;
heir->right = node->right;
*prev = heir;
}
}
free(node);
return 1;
}
/* b_delete.h */
#define DELETE --- /* <- ここに 数字を記入 */
$cc -c b_delete.c
$cc -o b_delete b_delete.o
$./b_delete < random.txt*1:$vi b_delete.h
