[C++知识库]二叉树实现

#include<stdio.h>
#include<stdlib.h>
 
#define NAMESIZE 32
 
struct score_st{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};
 
struct node_st{
    struct score_st data;
    struct node_st *l,*r;
};
 
void print_s(struct score_st *d)
{
    printf("%d %s %d %d\n", d->id, d->name, d->math, d->chinese);
}
 
int insert(struct node_st **root, struct score_st *data)
{
    struct node_st *node;
    if(*root == NULL)
    {
        node = malloc(sizeof(*node));
        if(node == NULL)
        {
            printf("malloc err!\n");
            return -1;
        }
        node->data = *data;
        node->l = NULL;
        node->r = NULL;
        *root = node;
        return 0;
    }
    if(data->id <= (*root)->data.id)
        return insert(&(*root)->l, data);
    else
        return insert(&(*root)->r, data);
}
 
struct score_st *find(struct node_st *root, int id)
{
    if(root == NULL)
        return NULL;
    if(id == root->data.id)
        return &root->data;
    if(id < root->data.id)
        return find(root->l, id);
    else
        return find(root->r, id);
}

void draw_(struct node_st *root, int level)
{
	int i;
	if(root == NULL)
		return;
	draw_(root->r, level+1);
	for(i = 0; i < level; i++)
        printf("  ");
	for(i = 0; i < level; i++)
		printf("  ");
	print_s(&root->data);
	for(i = 0; i < level; i++)
        printf("  ");
	draw_(root->l, level+1);
}
void draw(struct node_st *root)
{
	draw_(root,0);

}

int get_num(struct node_st *root)
{
	//int i = 0;
	if(root == NULL)
		return 0;
	else
		return 1 + get_num(&root->l) + get_num(&root->r); 
}

void turn_left(struct node_st **root)
{
	struct node_st **node = root;
	struct node_st *node1 = NULL;
	root = &((*root)->r);
	node->r = NULL;//这个不能忘

	node1 = (*root)->l;
	while(node1 != NULL)
		node1 = node1->l;
	node1 = *node;
}

//另外实现方法

struct node_st *find_l(struct node_st *root)
{
	if(root == NULL)
		return root;
	return find_l(&(root->l));
}
void turn_left(struct node_st **root)
{
	struct node_st *cur = *root;
	*root = cur->r;
	cur->r = NULL;

	find_l(*root)->l = cur;
}

void balance(struct node_st **root)
{
	if(*root == NULL)
		return;
	int sub;

	while(1)
	{
		sub = get_num(&(*root)->l) - get_num(&(*root)->r);
		if(sub >= -1 || sub <= 1)
			break;
		if(sub < -1)
			turn_left(root);
		if(sub > 1)
			turn_right(root);
	}
	balance(&(*root)->l);
	balance(&(*root)->r);
}

int main()
{
    int i;
    int arr[] = {1, 2, 3, 7, 6, 5, 9, 8, 4};
    struct node_st *tree = NULL;
    struct score_st tmp, *datap;
 
    for(i = 0; i < sizeof(arr)/sizeof(*arr); i++)
    {
        tmp.id = arr[i];
        snprintf(tmp.name, NAMESIZE, "stu%d", arr[i]);
        tmp.math = rand() % 100;
        tmp.chinese = rand() % 100;
        insert(&tree, &tmp);
    }
	draw(tree);
#if 0 
    int tmpid = 12;
    datap = find(tree, tmpid);
    if(datap == NULL)
        printf("can't find %d\n", tmpid);
    else
        print_s(datap);
#endif
 
}