毕业设计数据结构b类红黑二叉树Word格式文档下载.docx
《毕业设计数据结构b类红黑二叉树Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《毕业设计数据结构b类红黑二叉树Word格式文档下载.docx（33页珍藏版）》请在冰点文库上搜索。
StatusDestroyStack（LinkStack*L）;
StatusStackLength（LinkStack*L）;
StatusPushStack（LinkStack*L,RedBlackNode*r）;
RedBlackNode*PopStack（LinkStack*L）;
RedBlackNode*RBserach（RedBlackNode*rbtree,intkey）;
RedBlackNode*RBMinimum（RBTree*T）;
RedBlackNode*RBMaximum（RBTree*T）;
RedBlackNode*RBpioneer（RedBlackNode*T）;
RedBlackNode*RBsucceed（RedBlackNode*T）;
voidleft_rotate（RBTree*rbtree,RedBlackNode*T）;
voidright_rotate（RBTree*retree,RedBlackNode*T）;
BOOLRBInsertNode（RBTree*T,intdata）;
intRBDeleteNode（RBTree*T,intdata）;
voidRbTreeInsertAdjust（RBTree*T,RedBlackNode*p）;
voidRbTreeDeleteAdjust（RBTree*T,RedBlackNode*parent,RedBlackNode*x）;
voidOutput（RedBlackNode*p）;
voidPreorderTraverse（RedBlackNode*T）;
voidInorderTraverse（RedBlackNode*T）;
voidPostorderTraverse（RedBlackNode*T）;
intprerecursion（RedBlackNode*T）;
intinrecursion（RedBlackNode*T）;
intpostrecursion（RedBlackNode*T）;
voidmenu1（）;
voidmenu2（）;
voidlogon（）;
LinkStack*InitStack（）
LinkStack*L;
L=（LinkStack*）malloc（sizeof（LinkStack））;
L->
next=NULL;
returnL;
}
StatusStackEmpty（LinkStack*L）
if（L->
next）
{
returnFALSE;
}
else
returnTRUE;
StatusDestroyStack（LinkStack*L）
LinkStack*p,*r,*q;
p=L->
next;
r=L;
if（p==NULL）
returnFALSE;
while（p!
=NULL）
r->
next=p->
q=p;
p=p->
free（q）;
free（L）;
StatusStackLength（LinkStack*L）
inti=0;
LinkStack*p;
if（L==NULL）
i++;
p=p->
returni;
RedBlackNode*PopStack（LinkStack*L）
{
RedBlackNode*q;
p=L;
while（p->
next&
&
p->
next->
next!
q=p->
rbtree;
p->
returnq;
StatusPushStack（LinkStack*L,RedBlackNode*r）
LinkStack*p,*stacknode=（LinkStack*）malloc（sizeof（LinkStack））;
stacknode->
rbtree=r;
next=stacknode;
RedBlackNode*RBserach（RBTree*rbtree,intkey）//查找值为key的节点
RedBlackNode*T;
T=*rbtree;
while（T!
=NULL&
T->
data!
=key）
if（key<
data）
{
T=T->
left;
}
else
right;
Output（T）;
returnT;
RedBlackNode*RBMinimum（RBTree*T）//返回红黑树局部最小值
RedBlackNode*curNode,*targetNode;
curNode=*T;
targetNode=NULL;
if（curNode!
targetNode=curNode;
curNode=curNode->
returntargetNode;
RedBlackNode*RBMaximum（RBTree*T）//返回红黑树局部最大值
RedBlackNode*RBpioneer（RedBlackNode*T）//返回T的前驱
RedBlackNode*targetNode;
RedBlackNode*P;
P=NULL;
if（T==NULL）
returnP;
if（T->
left!
targetNode=RBMaximum（&
（T->
left））;
else
while（T->
parent!
parent->
right!
=T）
T=T->
parent;
targetNode=T->
RedBlackNode*RBsucceed（RedBlackNode*T）//后继节点
targetNode=RBMinimum（&
right））;
targetNode=T->
voidleft_rotate（RBTree*rbtree,RedBlackNode*T）//左旋
RedBlackNode*p;
p=T->
T->
right=p->
if（p->
p->
left->
parent=T;
parent=T->
parent==NULL）
{
*rbtree=p;
left==T）
T->
left=p;
right=p;
}
left=T;
parent=p;
voidright_rotate（RBTree*retree,RedBlackNode*T）
left=p->
right->
*retree=p;
right=T;
BOOLRBInsertNode（RBTree*T,intdata,char*name,char*phone）
RedBlackNode*node,*p,*curNode;
node=（RedBlackNode*）malloc（sizeof（RedBlackNode））;
if（node==NULL）
node->
data=data;
strcpy（node->
phone,phone）;
name,name）;
color=RED;
left=NULL;
right=NULL;
parent=NULL;
p=NULL;
while（curNode!
p=curNode;
if（data<
curNode->
*T=node;
if（data<
left=node;
}
right=node;
RbTreeInsertAdjust（T,node）;
intRBDeleteNode（RBTree*T,intdata,char*name,char*phone）
RedBlackNode*child,*target,*realdel;
target=RBserach（T,data）;
if（target!
if（target->
left==NULL||target->
right==NULL）
realdel=target;
realdel=RBsucceed（target）;
if（realdel->
child=realdel->
if（child!
child->
parent=realdel->
*T=child;
if（realdel->
left==realdel）
realdel->
left=child;
right=child;
=realdel）
target->
data=realdel->
data;
strcpy（target->
color==BlACK）
RbTreeDeleteAdjust（T,realdel->
parent,child）;
free（realdel）;
voidRbTreeInsertAdjust（RBTree*T,RedBlackNode*p）
RedBlackNode*q,*uncle,*grandparent;
while（（q=p->
parent）!
q->
color==RED）
grandparent=q->
if（q==grandparent->
left）
uncle=grandparent->
if（uncle!
uncle->
{
grandparent->
q->
color=BlACK;
uncle->
p=grandparent;
}
else
if（p==q->
right）
{
p=q;
left_rotate（T,p）;
q=p->
}
else
q->
grandparent->
right_rotate（T,grandparent）;
uncle=grandparent->
if（uncle!
grandparent->
q->
uncle->
p=grandparent;
if（p==q->
p=q;
right_rotate（T,p）;
q=p->
left_rotate（T,grandparent）;
（*T）->
voidRbTreeDeleteAdjust（RBTree*T,RedBlackNode*parent,RedBlackNode*x）
RedBlackNode*brother;
while（（x==NULL||x->
color==BlACK）&
x!
=*T）
if（x==parent->
brother=parent->
if（brother->
brother->
parent->
left_rotate（T,parent）;
brother=parent->
}
if（（brother->
left==NULL||brother->
（brother->
right==NULL||brother->
color==BlACK））
x=parent;
parent=parent->
if（brother->
brother->
right_rotate（T,brother）;
brother=parent->
color=parent->
color;
x=*T;
if（brother->
brother->
parent->
right_rotate（T,parent）;
if（（brother->
left_rotate（T,brother）;
right_rotate（T,parent）;
if（x!
x->
}
}
voidOutput（RedBlackNode*p）
printf（"
data:
%d,color:
%s,parent:
%d，name:
%s,phone:
%s\n"
data,（p->
color==RED?
"
RED"
:
BlACK"
）,
（p->
parent!
=NULL）?
data:
-1,p->
name,p->
phone）;
voidPreorderTraverse（RedBlackNode*T）
LinkStack*L=InitStack（）;
p=T;
while（p||!
StackEmpty（L））
while（p）//遍历左子树
Output（p）;
PushStack（L,p）;
if（!
StackEmpty（L））//通过下一次循环中的内嵌while实现右子树遍历
p=PopStack（L）;
voidInorderTraverse（RedBlackNode*T）
L=InitStack（）;
while（p!
=NULL||!
=NULL）//遍历左子树
PushStack（L,p）;
p=PopStack（L）;
Output（p）;
//访问根结点
//通过下一次循环实现右子树遍历
DestroyStack（L）;
voidPostorderTraverse
升级会员 