これはcの単純な二分木ですが、バランスが取れていないようです。どうすればバランスが取れますか?
コード：
/**
* binary_tree impl
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct _tnode _tnode;
typedef struct _bin_tree _bin_tree;
struct _tnode {
int data;
_tnode *parent;
_tnode *left;
_tnode *right;
};
_tnode *new_node(int data) {
_tnode *node = (_tnode*)malloc(sizeof(_tnode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
_tnode *add(_tnode *top, int new_data, int (*cmpf)(int, int)) {
if(top == NULL) {
top = new_node(new_data);
} else if(cmpf(top->data, new_data)<=0) {
if(top->left == NULL)
top->left = new_node(new_data);
else
add(top->left, new_data, cmpf);
} else {
if(top->right == NULL)
top->right = new_node(new_data);
else
add(top->right, new_data, cmpf);
}
return top;
}
int cmp_int(int n1, int n2) {
return n1 - n2;
}
void print_tree(_tnode *top) {
if(top->left) print_tree(top->left);
printf("%d\n",top->data);
if(top->right) print_tree(top->right);
}
int main(int argc, char * argv[]) {
int i = 0;
_tnode *top = NULL;
int arr[] = {6,1,9,3,5,0,2,7};
int count = sizeof(arr) / sizeof(arr[0]);
for(i=0; i<count; i++) {
top = add(top, arr[i], cmp_int);
printf("add: %d\n", arr[i]);
}
print_tree(top);
return 0;
}