[cpp]
#include
#include
#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;
}