平衡二叉树实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct node
{
int data;
int blance;
struct node * left;
struct node * right;
}node_t, * node_tp;
static node_tp avl_tab_p = NULL;
void init_node(node_tp node, int data)
{
if(node)
{
node->data = data;
node->blance = 0;
node->left = NULL;
node->right = NULL;
}
}
void free_tab_s(node_tp node)
{
if(!node)
return;
free_tab_s(node->left);
free_tab_s(node->right);
printf("\nfree data=%d", node->data);
free(node);
}
void free_tab(void)
{
free_tab_s(avl_tab_p);
avl_tab_p = NULL;
}
node_tp find_node(node_tp node, int data)
{
if(!node)
return node;
else if(node->data > data)
return find_node(node->left, data);
else if(node->data < data)
return find_node(node->right, data);
else
return node;
}
int node_depth(node_tp node, int * blance)
{
int l, r;
if(!node)
return 0;
l = node_depth(node->left, blance);
r = node_depth(node->right,blance);
if(blance && (l - r > 1 || l - r < -1))
{
*blance = 0;
printf("\ncha=%d, %d", l-r, node->data);
}
return 1 + ((l > r)? l:r);
}
int travesal_mid_s(node_tp node)
{
int l, r;
if(!node)
return 0;
l =
travesal_mid_s(node->left);
printf(" %d(blance=%d depth=%d,) ", node->data, node->blance,node_depth(node,NULL));
r = travesal_mid_s(node->right);
return l + r + 1;
}
void travesal_mid(void)
{
int blance = 1;
int depth = node_depth(avl_tab_p, &blance);
int count;
printf("\n---tree is:--------\n");
count = travesal_mid_s(avl_tab_p);
printf("\n-----count=%d----depth=%d----blance=%d-----------", count, depth, blance);
}
node_tp max_node(node_tp node)
{
if(!node || !node->right)
return node;
return max_node(node->right);
}
node_tp left_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->right && node->right->right)
{
p
= node->right;
node->right = p->left;
p->left = node;
if(p->blance == 0)
{
p->blance = -1;
p->left->blance = 1;
}
else
{
p->blance = 0;
p->left->blance = 0;
}
}
return p;
}
node_tp right_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->left && node->left->left)
{
p = node->left;
node->left = p->right;
p->right = node;
if(p->blance == 0)
{
p->blance = 1;
p->right->blance = -1;
}
else
{
p->blance = 0;
p->right->blance = 0;
}
}
return p;
}
node_tp left_right_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->left && node->left->right)
{
p = node->left->right;
node->left->right = p->left;
p->left = node->left;
node->left = p->right;
p->right = node;
switch(p->blance)
{
case -1:
p->left->blance = p->blance = 0;
p->right->blance = 1;
break;
case 0:
p->left->blance = p->right->blance = p->blance = 0;
break;
case 1:
p->left->blance = -1;
p->blance = p->right->blance = 0;
break;
default:
break;
}
}
return p;
}
node_tp right_left_rotate(node_tp node)
{
node_tp p = NULL;
if(node && node->right && node->right->left)
{
p = node->right->left;
node->right->left = p->right;
p->right = node->right;
node->right = p->left;
p->left = node;
switch(p->blance)
{
case -1:
p->left->blance = p->blance = 0;
p->right->blance = 1;
break;
case 0:
p->blance = p->left->blance = p->right->blance = 0;
break;
case 1:
p->blance = p->right->blance = 0;
p->left->blance = -1;
break;
default:
break;
}
}
return p;
}
int rotate_type(node_tp node)
{
if(!node)
return 0;
if(node->left && node->blance == -2 && node->left->blance <= 0)
return 1;
else if(node->right && node->blance == 2 && node->right->blance >= 0)
return -1;
else if(node->left && node->left->right && node->blance == -2 && node->left->blance
== 1)
return -2;
else if(node->right && node->right->left && node->blance == 2 && node->right->blance == -1)
return 2;
return 0;
}
node_tp avl_rotate(node_tp node)
{
switch(rotate_type(node))
{
case -1:
node = left_rotate(node);
break;
case 1:
node = right_rotate(node);
break;
case -2:
node = left_right_rotate(node);
break;
case 2:
node = right_left_rotate(node);
break;
default:
node = NULL;
break;
}
return node;
}
int insert_node_s(node_tp father_p, node_tp node, int data)
{
node_tp p;
int flag;
if(!father_p && !node)
{
p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, data);
avl_tab_p = p;
return 0;
}
if(!node)
return 1;
else if(node->data == data)
return -1;
else if(node->data > data)
flag = insert_node_s(node, node->left, data);
else
flag = insert_node_s(node, node->right, data);
if(flag <= 0)
return flag;
if(node->data > data && !node->left)
{
p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, data);
node->left = p;
}
else if(node->data < data && !node->right)
{
p = (node_tp)malloc(sizeof(node_t));
assert(p != NULL);
init_node(p, data);
node->right = p;
}
if(node->data >
data)
node->blance--;
else
node->blance++;
if(node->blance == -2 || node->blance == 2)
{
if(avl_tab_p == node)
{
avl_tab_p = avl_rotate(node);
node = avl_tab_p;
}
else
{
node = avl_rotate(node);
if(father_p->data > node->data)
father_p->left = node;
else
father_p->right = node;
}
}
if(node->blance == 0)
return 0;
else
return 1;
}
int insert_node(int data)
{
return (!insert_node_s(avl_tab_p, avl_tab_p, data) ? 0: -1);
}
int del_node_s(node_tp father_p, node_tp node, int data, node_tp deleted_node)
{
int flag;
int old_blance;
if(!father_p && !node)
return -1;
else if(!node)
return -1;
else if(node->data > data)
flag = del_node_s(node, node->left, data, deleted_node);
else if(node->data < data)
flag = del_node_s(node, node->right, data, deleted_node);
else
{
if(father_p == node)
avl_tab_p = NULL;
else
{
deleted_node->data = data;
if(father_p->left == node)
{
if(node->left)
father_p->left = node->left;
else
father_p->left = node->right;
}
else
{
if(node->left)
father_p->right = node->left;
else
father_p->right = node->right;
}
}
printf("\nfree data=%d", node->data);
free(node);
if(!avl_tab_p)
return 0;
else
return 1;
}
if(flag <= 0)
return flag;
old_blance = node->blance;
if(node->data >= data)
node->blance++;
else
node->blance--;
if(node->blance == -2 || node->blance == 2)
{
if(avl_tab_p == node)
{
avl_tab_p = avl_rotate(node);
node = avl_tab_p;
}
else
{
node = avl_rotate(node);
if(father_p->data > node->data)
father_p->left = node;
else
father_p->right = node;
}
}
if(old_blance == 0 || avl_tab_p == node)
return 0;
else
return 1;
}
int del_node(int data)
{
node_tp p, pre_p;
p = find_node(avl_tab_p, data);
if(!p)
return -1;
printf("\nfind node=%d", p->data);
pre_p =
max_node(p->left);
if(!pre_p)
pre_p = p;
printf("\nfind pre node=%d", pre_p->data);
return (!del_node_s(avl_tab_p, avl_tab_p,
pre_p->data, p)? 0: -1);
}
void input_data(void)
{
char str[20];
int data, ret;
for(ret = 0; ret < 11; ret++)
insert_node( ret);
travesal_mid();
while(1)
{
/*
printf("\n\n\nenter data =");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
travesal_mid();
ret = insert_node( data);
if(ret != -1)
printf("\n insert data=%d successful", data);
travesal_mid();
}
*/
printf("\n\n\ndel data =");
scanf("%s", str);
if(strncmp(str, "ok", 2) == 0)
break;
ret = sscanf(str, "%d", &data);
if(ret == 1)
{
travesal_mid();
ret = del_node( data);
if(ret != -1)
printf("\n del data=%d successful", data);
travesal_mid();
}
}
free_tab();
}
int main(int argc , char **argv)
{
input_data();
return 0;
}
2008-05-19 19:51
