. //by svking //2012.5
#include
#define MAXSIZE 1000 typedef int ElemType; #define RED 0 #define BLACK 1 typedef struct RBTNode {
char color; ElemType data; struct RBTNode * p; struct RBTNode * left; struct RBTNode * right; }RBTNode, * PRBTNode;
typedef struct RBTree {
PRBTNode root;
PRBTNode nil; //统一的空节点，该节点是黑的 }RBTree, * PRBTree;
int leftRotate (PRBTree tree, PRBTNode t); int rightRotate (PRBTree tree, PRBTNode t); PRBTNode insertRB (PRBTree tree, ElemType d); int insertRB_fixup (PRBTree tree, PRBTNode t); int createRBTree (PRBTree tree, ElemType d[], int n); int initRB (PRBTree tree);
PRBTNode maximum (PRBTree tree, PRBTNode t); PRBTNode minimum (PRBTree tree, PRBTNode t); PRBTNode next (PRBTree tree, PRBTNode t); PRBTNode precursor (PRBTree tree, PRBTNode t); int walkNext (PRBTree tree);
int inOrderWalk (PRBTree tree, PRBTNode t); int deleteRB_fixup (PRBTree tree, PRBTNode c); PRBTNode deleteRB (PRBTree tree, PRBTNode t); int main () {
PRBTNode p; int d[MAXSIZE]; int n = 0;
1 / 11
. int i; RBTree tree; initRB(&tree);
/* insertRB(&tree, 11); insertRB(&tree, 2); insertRB(&tree, 14);
insertRB(&tree, 1); insertRB(&tree, 7); insertRB(&tree, 15); insertRB(&tree, 5); insertRB(&tree, 8); insertRB(&tree, 4); */ p= insertRB(&tree, 26); insertRB(&tree, 17); insertRB(&tree, 41); insertRB(&tree, 14); insertRB(&tree, 21); insertRB(&tree, 30); insertRB(&tree, 47); insertRB(&tree, 10); insertRB(&tree, 16); insertRB(&tree, 19); insertRB(&tree, 23); insertRB(&tree, 28); insertRB(&tree, 38); insertRB(&tree, 7); insertRB(&tree, 12); insertRB(&tree, 15); insertRB(&tree, 20); insertRB(&tree, 3); insertRB(&tree, 35); insertRB(&tree, 39);
srand(time(NULL));
/* puts(\请输入数据的个数：\随机生成的%d个数据是：\\n\\建树开场\
inOrderWalk(&tree,tree.root); puts(\);
printf(\根是%d \\n\,tree.root->data);
printf(\删除%d后：\,p->data); deleteRB(&tree, p);
inOrderWalk(&tree,tree.root); puts(\);
printf(\根是%d \\n\,tree.root->data);
2 / 11
. return0; }
PRBTNode insertRB (PRBTree tree, ElemType d)
{//插入元素//!!!记得插入的元素的初始化，p指向为父母节点，left和right赋值为NULL。 PRBTNode t = NULL; PRBTNode p = NULL;
int flag = 0; //用来表示插入在左边的树还是右边的树 t = tree->root;
//插入的节点是root,并做相应的初始化if (tree->root == tree->nil) {
tree->root = (PRBTNode)malloc(sizeof(RBTNode)); tree->root->data = d; tree->root->color = BLACK;
tree->root->p = tree->root->left =tree->root->right = tree->nil;
return tree->root; }
while (t != tree->nil) {
p = t;
if (d < t->data) {
flag = 0; t = t->left; } else {
if (d > t->data) {
flag = 1; t = t->right; }else {
if ( (flag=rand()%2) == 0) t = t->left; else
t = t->right; } }
}//while //将t指向带插入节点的地址，并初始化 t = (PRBTNode)malloc(sizeof(RBTNode)); t->data = d;
3 / 11
红黑树的代码实现
