?? rbtree.h
字號:
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
typedef int status;
typedef int KeyType;//關鍵域數據類型;
typedef enum color
{
red,black
}color;
typedef struct RBTreeNode
{
KeyType key;
color clr;
struct RBTreeNode *parent;
struct RBTreeNode *lChild;
struct RBTreeNode *rChild;
}RBTreeNode,*pRBTreeNode;
status LeftRotate(RBTreeNode **tRoot,pRBTreeNode x)
{//左旋
if(x!=NULL&&x->rChild!=NULL)
{
pRBTreeNode y;
y=x->rChild;
x->rChild=y->lChild;
if(y->lChild!=NULL)
y->lChild->parent=x;
y->parent=x->parent;
if(x->parent==NULL)
{
(*tRoot)=y;
y->parent=NULL;
}
else if(x==x->parent->lChild)
x->parent->lChild=y;
else
x->parent->rChild=y;
y->lChild=x;
x->parent=y;
return OK;
}
else return FALSE;
}
status RightRotate(RBTreeNode **tRoot,pRBTreeNode y)
{//右旋
if(y!=NULL&&y->lChild!=NULL)
{
pRBTreeNode x=y->lChild;
y->lChild=x->rChild;
if(x->rChild!=NULL)
x->rChild->parent=y;
x->parent=y->parent;
if(y->parent==NULL)
{
(*tRoot)=x;
x->parent=NULL;
}
else if(y==y->parent->lChild)
y->parent->lChild=x;
else
y->parent->rChild=x;
x->rChild=y;
y->parent=x;
return OK;
}
else return FALSE;
}
status RBTInsertFixup(RBTreeNode **tRoot,pRBTreeNode z)
{//插入調整
pRBTreeNode y;
while(z->parent!=NULL&&z->parent->clr==red)
{
if(z->parent==z->parent->parent->lChild)
{
y=z->parent->parent->rChild;
if(y!=NULL&&y->clr==red)
{//情況1
z->parent->clr=black;
y->clr=black;
z->parent->parent->clr=red;
z=z->parent->parent;
}
else
{
if(z==z->parent->rChild)
{//情況2
z=z->parent;
LeftRotate(tRoot,z);
}
//情況3
z->parent->clr=black;
z->parent->parent->clr=red;
RightRotate(tRoot,z->parent->parent);
}
}
else
{
y=z->parent->parent->lChild;
if(y!=NULL&&y->clr==red)
{//情況4
z->parent->clr=black;
y->clr=black;
z->parent->parent->clr=red;
z=z->parent->parent;
}
else
{
if(z==z->parent->lChild)
{//情況5
z=z->parent;
RightRotate(tRoot,z);
}
//情況6
z->parent->clr=black;
z->parent->parent->clr=red;
LeftRotate(tRoot,z->parent->parent);
}
}
}
(*tRoot)->clr=black;
return OK;
}
status RBTInsert(RBTreeNode **tRoot,pRBTreeNode z)
{//紅黑樹插入
pRBTreeNode y=NULL;
pRBTreeNode x=*tRoot;
while(x!=NULL)
{
y=x;
if(z->key<x->key)
x=x->lChild;
else
x=x->rChild;
}
z->parent=y;
if(y==NULL)
{
*tRoot=z;
z->parent=NULL;
}
else if(z->key<y->key)
y->lChild=z;
else
y->rChild=z;
z->lChild=NULL;
z->rChild=NULL;
z->clr=red;
RBTInsertFixup(tRoot,z);
return OK;
}
status InorderRBTWalk(pRBTreeNode tRoot)
{//中序遍歷
if(tRoot!=NULL)
{
InorderRBTWalk(tRoot->lChild);
printf("key=%d,",tRoot->key);
if(tRoot->clr==0)
printf("color:red ");
else
printf("color:black ");
InorderRBTWalk(tRoot->rChild);
}
return OK;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -