《红黑树的代码实现》由会员分享，可在线阅读，更多相关《红黑树的代码实现（18页珍藏版）》请在金锄头文库上搜索。
1、/by svking/2012.5#include #include #include #define MAXSIZE 1000typedef int ElemType;#define RED 0#defineBLACK 1typedef structRBTNodecharcolor;ElemTypedata;structRBTNode*p;structRBTNode*left;structRBTNode*right;RBTNode, * PRBTNode;typedef struct RBTreePRBTNode root;PRBTNode nil;/统一的空节点，该节点是黑的RBTree,
2、 * 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, PRBTN
3、ode 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);
4、int main ()PRBTNode p;int dMAXSIZE;int n =0;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);ins
5、ertRB(&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)
6、;insertRB(&tree,35);insertRB(&tree,39);srand(time(NULL);/*puts(请输入数据的个数：”)；scanf(%d,&n);printf(”随机生成的%d个数据是：n,n);for (i = 0; i data);printf(删除%d后：,p-data);deleteRB(&tree, p);inOrderWalk(&tree,tree.root);puts( );printf(根是 %d n ,tree.root-data);return0;PRBTNode insertRB (PRBTree tree, ElemType d)/插入元素
7、/!记得插入的元素的初始化，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-rig
8、ht = tree-nil;return tree-root;while (t != tree-nil)p = t;if (d data)flag =0 ；t = t-left;elseif (d t-data)flag =1 ；t = t-right;elseif ( (flag=rand()%2) =0)t = t-left;elset = t-right; /while/ 将t指向带插入节点的地址，并初始化t = (PRBTNode)malloc(sizeof (RBTNode);t-data = d;t-color = RED;t-p = p;t-left = t-right = tr
9、ee-nil;if (!flag)p-left = t;elsep-right = t;insertRB_fixup(tree, t);return t; int insertRB_fixup (PRBTree tree, PRBTNode t)/插入的节点可能破坏红黑树的性质。该函数检测插入的节点是否破坏了红黑树的性质。如果破坏了, 就对树进行调整，使其满足红黑树的性质while (t-p-color = RED)/只有插入节点的父亲是红色的才会破坏红黑树的性质(4.如果一个结点是红的，那么它的俩个儿子都是黑的)if (t-p-p-left = t-p)/插入节点的父节点本身是left/ca
10、se 1if (t-p-p-right-color = RED)t = t-p-p;t-left-color = t-right-color = BLACK;t-color = RED;elseif (t-p-right = t)/case 2/ 将 case 2 转换为了 case 3t = t-p;/这步赋值是为了在转换为case 3时，t指向的是下面的红节点，和case 3的情况相一致leftRotate(tree, t);/case 3t-p-color = BLACK;t-p-p-color = RED;rightRotate(tree, t-p-p); /ifelse /插入节点的
11、父节点本身是rightif (t-p-p-left-color = RED)/case 1t = t-p-p;t-left-color = t-right-color = BLACK;t-color = RED;elseif (t-p-left = t)/case 2/ 将 case 2 转换为了 case 3t = t-p;/这步赋值是为了在转换为case 3时，t指向的是下面的红节点，和case 3的情况相一致rightRotate(tree, t);/case 3t-p-color = BLACK;t-p-p-color = RED;leftRotate(tree, t-p-p); /e
12、lse /while tree-root-color = BLACK;return 0;int leftRotate (PRBTree tree, PRBTNode t)PRBTNode c;/ 左旋,c 指向 t 的 rightc = t-right;if (t-right = tree-nil)/ 左旋，t 的 right不能为空return 1;/这个if-else 用于将t的父亲节点的left 或right 点指向c，如果t的父节点为不存在，则树的root 指向cif (t-p != tree-nil)/ 判断 t 是否为 rootif (t-p-left = t)/判断t是t的父节点
13、的left 还是rightt-p-left = c;elset-p-right = c;elsetree-root = c;c-p = t-p;/更新 c的父节点t-right = c-left;if (c-left != tree-nil)c-left-p = t;c-left = t;t-p = c;return 0;int rightRotate (PRBTree tree, PRBTNode t)PRBTNode c;/ 右旋，c 指向 t 的 leftc = t-left;if (t-left = tree-nil)/ 右旋，t 的 left不能为空return 1;/这个if-else 用于将t的父亲节点的left 或right 点指向c，如果t的父节点为不存在，则树的root 指向cif (t-p != tree-nil)/ 判断 t 是否为 rootif (t-p-left = t)
