下面是源程序： [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; } }
