频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
红黑树的创建+线索化+性质检验+笔画输入法
2013-02-05 15:07:11      个评论      
收藏   我要投稿
下面是源程序:

[cpp] 

#include <stdio.h>  

#include <stdlib.h>  

  

#define TRUE  1  

#define FALSE 0  

#define HANZINUM 4762  

#define HANZILENGTH 4  

#define BIHUALENGTH 30  

  

char bihuaArr[HANZINUM][BIHUALENGTH];  

char hanziArr[HANZINUM][4];  

int first = 1;  

int num = 0;  

  

typedef struct bihuaData{  

    char data[4];  

    char bihua[30];  

}bihuaData;  

  

typedef int BOOL;  

typedef bihuaData ElemType;  

enum COLOR {Red, Black};  

enum pointerTag {Link, Thread};  

  

typedef struct RedBlackNode{  

    ElemType data;  

    struct RedBlackNode *left;  

    struct RedBlackNode *right;  

    struct RedBlackNode *p;  

    char color;//Red, Black  

    char ltag;  

    char rtag;  

}RedBlackNode, *RedBlackTree;  

  

BOOL find(RedBlackTree root, const ElemType x);  

void pprint(RedBlackTree root, int i);  

  

void makeEmpty(RedBlackNode *t);  

void left_rotate(RedBlackTree *t, RedBlackNode *x);  

void right_rotate(RedBlackTree *t, RedBlackNode *x);  

void rb_insert(RedBlackTree *root, RedBlackNode *t);  

void rb_insert_fixup(RedBlackTree *root, RedBlackNode *z);  

int compare(RedBlackNode *y, RedBlackNode *z);  

void creat_rb_tree(RedBlackTree * root);  

BOOL check_rb_tree(RedBlackTree root);  

void check_black_num(RedBlackTree root, int n);  

void inorder_traverse_rb_tree(RedBlackTree root);  

void negative_inorder_traverse_rb_tree(RedBlackTree root);  

void inorder_threading_rb_tree(RedBlackTree *thrt, RedBlackTree root);  

  

int main(){  

    RedBlackTree rbTree = NULL;  

    creat_rb_tree(&rbTree);  

    //check_rb_tree(rbTree);  

}  

  

void creat_rb_tree(RedBlackTree * root)  

{  

    FILE *fp = NULL;  

    char *file = "./bihuabishun.txt";  

    char *file3 = "./bihuahanzi.txt";  

    int i;  

    RedBlackNode *p = NULL;  

    RedBlackTree thrt;  

    freopen("data.out", "w", stdout);  

    fp = fopen(file, "rb");  

    if (fp == NULL)  

    {  

        printf("exit!\n");  

        exit(0);  

    }  

    fread(bihuaArr, BIHUALENGTH, HANZINUM, fp);  

    fclose(fp);  

    fp = fopen(file3, "rb");  

    if (fp == NULL)  

    {  

        printf("exit!\n");  

        exit(0);  

    }  

    fread(hanziArr, 4, HANZINUM, fp);  

    fclose(fp);  

      

    for (i = 0 ; i < HANZINUM; i++)  

    {  

        if (strcmp(bihuaArr[i], "") != 0 && strcmp(hanziArr[i], "") != 0)  

        {  

            p = (RedBlackNode *)malloc(sizeof(RedBlackNode));  

            if(p == NULL)  

            {  

              printf("exit!\n");  

             exit(0);  

            }  

            memset(p, 0, sizeof(RedBlackNode));  

            strcpy(p->data.data, hanziArr[i]);  

            strcpy(p->data.bihua, bihuaArr[i]);  

            rb_insert(root, p);  

            if(i == 4760){  

                inorder_threading_rb_tree(&thrt, *root);  

                negative_inorder_traverse_rb_tree(thrt);  

            }  

        }  

    }  

}  

  

void left_rotate(RedBlackTree *t, RedBlackNode *x)  

{  

    RedBlackNode * y = NULL;  

    y = x->right;  

    x->right = y->left;  

    if(y->left != NULL)  

    {  

        y->left->p = x;  

    }  

    y->p = x->p;  

    if(x->p == NULL)  

    {  

        *t = y;  

    }  

    else if(x == x->p->left)  

    {  

        x->p->left = y;     

    }  

    else  

    {  

        x->p->right = y;  

    }  

    y->left = x;  

    x->p = y;  

}  

  

void right_rotate(RedBlackTree *t, RedBlackNode *x)  

{  

    RedBlackNode * y = NULL;  

    y = x->left;  

    x->left = y->right;  

    if(y->right != NULL)  

    {  

        y->right->p = x;  

    }  

    y->p = x->p;  

    if(x->p == NULL)  

    {  

        *t = y;  

    }  

    else if(x == x->p->left)  

    {  

        x->p->left = y;     

    }  

    else  

    {  

        x->p->right = y;  

    }  

    y->right = x;  

    x->p = y;  

}  

  

void makeEmpty(RedBlackNode *t){  

    if(t != NULL){  

        makeEmpty(t->left);  

        makeEmpty(t->right);  

        free(t);  

    }  

    t = NULL;  

}  

  

void rb_insert(RedBlackTree *root, RedBlackNode *z)  

{  

    RedBlackNode *x = NULL, *y = NULL;  

      

    y = NULL;  

    x = *root;  

    while(x != NULL)  

    {  

        y = x;  

        if(compare(x, z) == 0)  

        {  

            return;  

        }  

        else if(compare(x, z) > 0)  

        {  

            x = x->left;  

        }  

        else if(compare(x, z) < 0)  

        {  

            x = x->right;  

        }  

    }  

    z->p = y;  

    if(y == NULL)  

    {  

        *root = z;  

    }  

    else if(compare(y, z) == 0)  

    {  

        return;  

    }  

    else if(compare(y, z) > 0)  

    {  

        y->left = z;  

    }  

    else if(compare(y, z) < 0)  

    {  

        y->right = z;  

    }  

    z->left = NULL;  

    z->right = NULL;  

    z->color = Red;  

    rb_insert_fixup(root, z);  

}  

  

void pprint(RedBlackTree root, int i){  

    if(root){  

        if(root->p != NULL)    

{  

num = num > i? num : i;}  

        pprint(root->left, i+1);  

        pprint(root->right, i+1);  

    }  

}  

  

int compare(RedBlackNode *y, RedBlackNode *z)  

{  

    if(strlen(y->data.bihua) ==  strlen(z->data.bihua))  

    {  

        return strcmp(y->data.bihua, z->data.bihua);  

    }  

    return strlen(y->data.bihua) - strlen(z->data.bihua);  

}  

  

void rb_insert_fixup(RedBlackTree *root, RedBlackNode *z)  

{  

    RedBlackNode *y = NULL;  

    while(z->p != NULL && z->p->color == Red)  

    {  

        if(z->p == z->p->p->left)  

        {  

            y = z->p->p->right;  

            if(y == NULL)  

            {  

                if( z == z->p->right)  

                {  

                    z = z->p;  

                    left_rotate(root, z);  

                    z->p->color = Black;  

                    z->p->p->color = Red;  

                    right_rotate(root, z->p->p);    

                }  

                else if( z == z->p->left)  

                {  

                    z->p->color = Black;  

                    z->p->p->color = Red;  

                    right_rotate(root, z->p->p);  

                    return;  

                }     

            }  

            else  

            {  

                if(y->color == Red)  

                {  

                    z->p->color = Black;  

                    y->color = Black;  

                    z->p->p->color = Red;  

                    z = z->p->p;  

                }  

                else   

                {  

                    if( z == z->p->right)  

                    {  

                        z = z->p;  

                        left_rotate(root, z);  

                    }  

                    z->p->color = Black;  

                    z->p->p->color = Red;  

                    right_rotate(root, z->p->p);    

                }         

            }  

        }  

        else  

        {  

            y = z->p->p->left;  

            if(y == NULL)  

            {     

                if( z == z->p->right)  

                {  

                    z->p->color = Black;  

                    z->p->p->color = Red;  

                    left_rotate(root, z->p->p);  

                    return;  

                }  

                else if( z == z->p->left)  

                {  

                    z = z->p;  

                    right_rotate(root, z);  

                    z->p->color = Black;  

                    z->p->p->color = Red;  

                    left_rotate(root, z->p->p);     

                }  

            }  

            else  

            {  

                if(y->color == Red)  

                {  

                    z->p->color = Black;  

                    y->color = Black;  

                    z->p->p->color = Red;  

                    z = z->p->p;  

                }  

                else  

                {  

                    if( z == z->p->left)  

                    {  

                        z = z->p;  

                        right_rotate(root, z);  

                    }  

                    z->p->color = Black;  

                    z->p->p->color = Red;  

                    left_rotate(root, z->p->p);  

                }  

            }  

        }  

    }  

    (*root)->color = Black;  

}  

  

void check_rb_tree_child(RedBlackTree root, int i)  

{  

    if(root->color == Red && root->left != NULL && root->right != NULL)  

    {  

        if(root->left->color == Black && root->right->color == Black)  

        {  

        }  

        else printf("9\n");  

    }  

      

    if(root->left != NULL)  

    {  

        check_rb_tree_child(root->left, i + 1);  

    }  

    if(root->right != NULL)  

    {  

        check_rb_tree_child(root->right, i + 1);  

    }  

}  

  

BOOL check_rb_tree(RedBlackTree root)  

{  

    int i = 0;  

    if(root->color == Red)  

    {  

        printf("root ERR!\n");  

        return 1;  

    }  

    check_rb_tree_child(root, ++i);  

    return 0;  

}  

  

void check_black_num(RedBlackTree root, int n)  

{  

    if(root == NULL)  

    {  

        printf("%d  \n", n);      

    }else  

    {  

        if(root->color == Black)  

        {  

            n+=1;  

        }  

        check_black_num(root->left, n);  

        check_black_num(root->right, n);   

    }  

}  

  

void inorder_traverse_rb_tree(RedBlackTree root)  

{  

    RedBlackNode *p = NULL;  

      

    p = root->left;  

      

    while(p != root)  

    {  

        while(p->ltag == Link)  

        {  

            p = p->left;  

        }  

        printf("%s\n",p->data.bihua);  

        while(p->rtag == Thread && p->right != root)  

        {  

            p = p->right;  

            printf("%s\n",p->data.bihua);  

        }  

        p = p->right;  

    }  

}  

  

void negative_inorder_traverse_rb_tree(RedBlackTree root)  

{  

    RedBlackNode *p = NULL;  

      

    p = root->right;  

      

    while(p != root)  

    {  

        while(p->rtag == Link)  

        {  

            p = p->right;  

        }  

        printf("%s\n",p->data.bihua);  

        while(p->ltag == Thread && p->left != root)  

        {  

            p = p->left;  

            printf("%s\n",p->data.bihua);  

        }  

        p = p->left;  

    }  

}  

  

void InThreading(RedBlackTree p, RedBlackTree * pre)  

{  

    if(p)  

    {  

        InThreading(p->left, pre);  

        if(p->left == NULL)  

        {  

            p->ltag = Thread;  

            p->left = *pre;  

        }  

        if((*pre)->right == NULL)  

        {  

            (*pre)->rtag = Thread;  

            (*pre)->right = p;  

        }  

        (*pre) = p;  

        InThreading(p->right, pre);  

    }  

}  

  

void inorder_threading_rb_tree(RedBlackTree *thrt, RedBlackTree root)  

{  

    RedBlackNode * pre = NULL;  

      

    *thrt = (RedBlackNode *)malloc(sizeof(RedBlackNode));  

    if(*thrt == NULL)  

    {  

      printf("exit!\n");  

     exit(0);  

    }  

    memset(*thrt, 0, sizeof(RedBlackNode));  

      

    (*thrt)->ltag = Link;  

    (*thrt)->rtag = Thread;  

    (*thrt)->right = (*thrt);  

    if(root == NULL)(*thrt)->left = (*thrt);  

    else  

    {  

        (*thrt)->left = root;  

        pre = (*thrt);  

        InThreading(root, &pre);  

        pre->right = (*thrt);  

        pre->rtag = Thread;  

        (*thrt)->right = pre;  

    }     

}  

 

点击复制链接 与好友分享!回本站首页
上一篇:hdu 称乒乓球
下一篇:270B Multithreading
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站