はじめての C
balance tree だけど、tutorial では 構造体 Tree を 使って、root を 返すようにしている。
それと、関数 norm_insert の中の new_node の 引数が、このままだと 1つ 足らない。
Tree は Node と 入れ換えれば、そのまま 使えるようなので、あとは norm_insert を ちょっと いじって、コードを 作成。
/* t_balance.c */
#include
#include struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Tree {
struct Node *root;
};
int norm_insert();
void btree_walk();
int tree_height();
void rotate_right();
void rotate_left();
int count();
void partition();
void balance();
main()
{
int value;
struct Tree *root;
root = NULL;
while (fscanf(stdin, "%d", &value) != EOF)
norm_insert(&root, value);
btree_walk(root);
putchar('\n');
printf("%d\n", tree_height(root));
puts("balancing now");
balance(&root);
printf("%d\n", tree_height(root));
return 0;
}
int norm_insert(struct Node **tree, int key)
{
int rc;
if (*tree == NULL) {
*tree = malloc(sizeof(**tree));
if (*tree == NULL)
rc = 0;
(*tree)->data = key;
(*tree)->left = NULL;
(*tree)->right = NULL;
rc = 1;
}
else if (key < (*tree)->data)
rc = norm_insert(&(*tree)->left, key);
else if (key > (*tree)->data)
rc = norm_insert(&(*tree)->right, key);
else
rc = 0;
return rc;
}
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;
}
void rotate_right(struct Node **root)
{
struct Node *save;
save = (*root)->left;
(*root)->left = save->right;
save->right = *root;
*root = save;
}
void rotate_left(struct Node **root)
{
struct Node *save;
save = (*root)->right;
(*root)->right = save->left;
save->left = *root;
*root = save;
}
int count(struct Node *tree)
{
if (tree == NULL)
return 0;
return count(tree->left) * count(tree->right) + 1;
}
void partition(struct Node **tree, int n)
{
int nleft = count((*tree)->left);
int nright = count((*tree)->right);
if (nleft > n) {
partition(&(*tree)->left, n);
rotate_right(tree);
}
if (nright > n) {
partition(&(*tree)->right, n);
rotate_left(tree);
}
}
void balance(struct Node **tree)
{
int n = count(*tree);
if (n < 2)
return;
partition(tree, n/2);
balance(&(*tree)->left);
balance(&(*tree)->right);
}
$cc -c t_balance.c
$cc -o t_balance t_balance.o
$./t_balance < random.txt
$./t_balance
0 1 2 3 4 5 (← ctrl + d)
0 1 2 3 4 5
5
balancing now
5