はじめての C
二分木の挿入プログラムが やっと できた ...
/* b_insert.c */
#include
#include struct Node {
int data;
struct Node *left;
struct Node *right;
};
int new_node();
int tree_insert();
void btree_walk();
int tree_height();
main()
{
int value;
struct Node *root;
root = NULL;
while (scanf("%d", &value) != EOF)
tree_insert(&root, value);
btree_walk(root);
putchar('\n');
printf("%d\n", tree_height(root));
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_height(struct Node *tree)
{
int left_height;
int right_height;
if (tree == NULL)
return -1;
left_height = tree_height(tree->left);
right_height = tree_height(tree->right);
if (left_height < right_height)
return right_height + 1;
else
return left_height + 1;
}
$cc -c b_insert.c
$cc -o b_insert b_insert.o
$./b_insert < random.txt