关于二叉树实现的几个应用范例(c语言)
简单点的,做练习用的,谢了

#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;
}