</pre><p>参考文件： <a target=_blank href="http://www.soft568.com/info/detail/4-11258.html">http://www.soft568.com/info/detail/4-11258.html</a></p><p align="left"><span style="color:#666666;">在</span><span style="color:#666666;">VC</span><span style="color:#666666;">环境下编译。主体语言是</span><span style="color:#666666;">C</span><span style="color:#666666;">，用到了点</span><span style="color:#666666;">C++</span><span style="color:#666666;">语法。</span></p><p align="left"><span style="color:#666666;"> </span></p><p align="left"><span style="color:#666666;">由于红黑树中的元素必须各不相同，定义了一个时间复杂度仅为</span><span style="color:#666666;">O</span><span style="color:#666666;">（</span><span style="color:#666666;">n</span><span style="color:#666666;">）的随机数产生函数：</span></p><p align="left"><span style="color:#666666;">void Random(int *A, int max, int length);</span></p><p align="left"><span style="color:#666666;">该函数能返回一个长度为</span><span style="color:#666666;">length,</span><span style="color:#666666;">元素随机分布在</span><span style="color:#666666;">0~max</span><span style="color:#666666;">之间的数组</span><span style="color:#666666;">A</span><span style="color:#666666;">。</span></p><p align="left"><span style="color:#666666;">根据实验主要功能</span><span style="color:#666666;">—</span><span style="color:#666666;">插入，定义了插入函数</span></p><p align="left"><span style="color:#666666;">void rbInsert(RBT* *root, RBT* pZ); </span></p><p align="left"><span style="color:#666666;">而插入函数需要调整红黑树结构，定义红黑树调整函数：</span></p><p align="left"><span style="color:#666666;">void rbFixUp(RBT **root, RBT *pZ);//</span><span style="color:#666666;">插入后的调整</span></p><p align="left"><span style="color:#666666;">在调整函数中又需要调用左旋操作和右旋操作：</span></p><p align="left"><span style="color:#666666;">void leftRotate(RBT* *root, RBT *pX); //</span><span style="color:#666666;">左旋操作</span></p><p align="left"><span style="color:#666666;">void rightRotate(RBT** root, RBT *pX); //</span><span style="color:#666666;">右旋操作</span></p><p align="left"><span style="color:#666666;">为了显示红黑树而定义了先序遍历的红黑树打印函数：</span></p><p align="left"><span style="color:#666666;">void treePrint(RBT **root); //</span><span style="color:#666666;">打印一棵树</span><span style="color:#666666;">,</span><span style="color:#666666;">先序遍历</span></p><p align="left"><span style="color:#666666;">打印红黑树的过程中需要调用对每一个结点的打印函数：</span></p><p align="left"><span style="color:#666666;">void rbPrint(RBT* pX); //</span><span style="color:#666666;">打印一个结点</span></p><p align="left"><span style="color:#333333;"></span><span style="color:#333333;">代码如下：</span><span style="color:#333333;"></span><span style="color:#333333;"></span><pre name="code" class="cpp">#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;#define red 0
#define black 1
#define SIZE 10 //待插入的元素个数
#define MAX 100 //待插入元素的范围0~MAX
typedef struct RB
{int key; //关键字int color; //颜色struct RB *ptParent; //指向父结点的指针struct RB *ptLeft; //指向左孩子的指针struct RB *ptRight; //指向右防子的指针
}RBT; //定义结构体RBT来表示红黑树一个结点void leftRotate(RBT* *root, RBT *pX); //左旋操作
void rbFixUp(RBT **root, RBT *pZ);//插入后的调整
void rightRotate(RBT** root, RBT *pX); //右旋操作
void rbInsert(RBT* *root, RBT* pZ); //插入操作
void rbPrint(RBT* pX); //打印一个结点
void treePrint(RBT **root); //打印一棵树,先序遍历
void Random(int *A, int max, int length);//产生一个长度为length数组,//数组元素随机分布在0~max间,且不重复,//时间复杂度为O(max)int main()
{RBT **root; //root指向根结点root = (RBT**)malloc(sizeof(RBT*));*root = NULL;//初始时树为空int *A; //A用来存放待入元素A = (int*)malloc(sizeof(int)*SIZE);int i;
/* for(i=0; i<SIZE; i++){A[i] = rand()%100;printf("%d ", A[i]);}*/Random(A, MAX, SIZE);for(i=0; i<SIZE; i++){printf("%d ", A[i]);}puts("\n");for(i=0; i<SIZE; i++){RBT *pZ = (RBT*)malloc(sizeof(RBT));//定义一个指向新结点的指针pZprintf("\nNow insert the element %d:\n", A[i]);pZ->key = A[i];rbInsert(root, pZ);treePrint(root);//打印当前红黑树结构system("pause");}puts("\nThe total tree is:\n ");treePrint(root);system("pause");return 0;
}//以下的各函数的定义//左旋
void leftRotate(RBT* *root, RBT* pX)
{RBT* pY;pY = pX->ptRight;if(pX->ptRight != NULL && pY != NULL)pX->ptRight = pY->ptLeft;if(pY != NULL && pY->ptLeft != NULL)pY->ptLeft->ptParent = pX; //将Y的左孩子变成X的右孩子if(pY != NULL)pY->ptParent = pX->ptParent;if(pX->ptParent == NULL)*root = pY; //如果pX结点是根那么让pY成为新的根else {if(pX == pX->ptParent->ptLeft)pX->ptParent->ptLeft = pY;elsepX->ptParent->ptRight = pY;}if(pY!=NULL)pY->ptLeft = pX;pX->ptParent = pY;
}//右旋
void rightRotate(RBT** root, RBT *pX)
{RBT* pY;pY = pX->ptLeft;if(pX->ptLeft != NULL && pY != NULL)pX->ptLeft = pY->ptRight;if(pY->ptRight != NULL && pY->ptLeft != NULL)pY->ptRight->ptParent = pX; //将Y的右孩子变成X的左孩子pY->ptParent = pX->ptParent;if(pX->ptParent == NULL)*root = pY; //如果pX结点是根那么让pY成为新的根else {if(pX == pX->ptParent->ptLeft)pX->ptParent->ptLeft = pY;elsepX->ptParent->ptRight = pY;}pY->ptRight = pX;pX->ptParent = pY;
}//红黑树插入
void rbInsert(RBT* *root, RBT* pZ)
{RBT *pY, *pX;pY = NULL;pX = *root;while(pX != NULL){pY = pX;if(pZ->key < pX->key)pX = pX->ptLeft;elsepX = pX->ptRight;}pZ->ptParent = pY;if(pY == NULL)*root = pZ;else{if(pZ->key < pY->key)pY->ptLeft = pZ;elsepY->ptRight = pZ;}pZ->ptLeft = pZ->ptRight = NULL;pZ->color = red;rbFixUp(root,pZ);}//红黑树调整
void rbFixUp(RBT **root, RBT *pZ)
{if(*root != NULL){RBT *pY;while(pZ->ptParent != NULL && pZ->ptParent->color == red){if(pZ->ptParent->ptParent->ptLeft == pZ->ptParent){pY = pZ->ptParent->ptParent->ptRight; //Y是Z的叔叔if(pY!=NULL && pY->color == red)//第一种情况 {pZ->ptParent->color = pY->color = black;pZ->ptParent->ptParent->color = red;pZ = pZ->ptParent->ptParent; //上溯到Z的爷爷,再进行调整}else //第二 三种情况{if(pZ == pZ->ptParent->ptRight) //case2->case3{pZ = pZ->ptParent;leftRotate(root, pZ);}pZ->ptParent->color = black;pZ->ptParent->ptParent->color = red;rightRotate(root, pZ->ptParent->ptParent);}}else{pY = pZ->ptParent->ptParent->ptLeft;if(pY != NULL && pY->color == red){pZ->ptParent->color = pY->color = black;pZ->ptParent->ptParent->color = red;pZ = pZ->ptParent->ptParent;}else{if(pZ == pZ->ptParent->ptLeft){pZ = pZ->ptParent;rightRotate(root, pZ);}pZ->ptParent->color = black;pZ->ptParent->ptParent->color = red;leftRotate(root,pZ->ptParent->ptParent);}}}(*root)->color = black;}
}//打印结点
void rbPrint(RBT* pX)
{if(pX !=NULL){printf("key: %d\t", pX->key);if(pX->color == red)printf("color: red\t");elseprintf("color: black\t");if(pX->ptLeft != NULL)printf("left: %d \t", pX->ptLeft->key);elseprintf("left: nil\t");if(pX->ptRight != NULL)printf("right: %d\t", pX->ptRight->key);elseprintf("right: nil\t");if(pX->ptParent != NULL)printf("parent: %d\t", pX->ptParent->key);elseprintf("*root\t");}elseprintf("empty");puts("\n");
}//从根结点开始先序遍历,打印树
void treePrint(RBT** root)
{if(*root != NULL){rbPrint(*root);treePrint(&((*root)->ptLeft));treePrint(&((*root)->ptRight));}
}//产生一个长度为length,元素随机分布在0~max之间的数组Avoid Random(int *A, int max, int length)
{srand(time(NULL));int i;int c;int k = max+1;int *B = (int*)malloc(sizeof(int)*k);for(i=0; i<k; i++)B[i] = i;for(i=0; i<length; i++){c = rand()%k;k--;A[i] = B[c];B[c] = B[k];}
}
程序编译通过,正常运行.
随机产生的待插入元素为：
54 62 81 91 34 9 16 74 48 24
最后输出结果为：
The total tree is:
key: 62 color: black left: 34 right:81 *root
key: 34 color:red left:16 right:54 parent: 62
key: 16 color: black left: 9 right:24 parent: 34
key: 9 color:red left: nil right: nil parent: 16
key: 24 color:red left: nil right: nil parent: 16
key: 54 color: black left: 48 right:nil parent: 34
key: 48 color:red left: nil right: nil parent: 54
key: 81 color: black left: 74 right:91 parent: 62
key: 74 color:red left: nil right: nil parent: 81
key: 91 color:red left: nil right: nil parent: 81
最终输出满足红黑树性质。
且中间每一步输出正确。
主函数int main()
{ …
return 0;
}
The thread 0x924 has exited with code 0(0x0).
The program 'D:\PhanYoung\课堂\Algorithm\实验\实验二红黑树的插入\Debug\rbt.exe'has exited with code 0 (0x0).
函数正常结束．获得正确结果．