【数据结构】b类—红黑二叉树正文终稿.doc

#include<stdio.h>

#include<malloc.h>

#include<string.h>

#include<windows.h>

#include <stdlib.h>

#define TRUE 1

#define BOOL int

#define FALSE 0

#define Status int

int data;

char phone[12];

char name[12]; //数据域

color_t color; //颜色

RedBlackNode *left; //左孩子

RedBlackNode *right; //右孩子

RedBlackNode *parent; //父亲节点

}RedBlackNode,*RBTree;

typedef struct LinkStack

{

Status StackLength(LinkStack *L);

Status PushStack(LinkStack *L,RedBlackNode *r);

RedBlackNode * PopStack(LinkStack *L);

RedBlackNode *RBserach(RedBlackNode *rbtree,int key);

RedBlackNode *RBMinimum(RBTree *T);

RedBlackNode *RBMaximum(RBTree *T);

RedBlackNode *RBpioneer(RedBlackNode *T);

RedBlackNode *RBsucceed(RedBlackNode *T);

void left_rotate(RBTree *rbtree,RedBlackNode *T);

void right_rotate(RBTree *retree,RedBlackNode *T);

BOOL RBInsertNode(RBTree *T,int data);

int RBDeleteNode(RBTree *T, int data);

void RbTreeInsertAdjust(RBTree *T,RedBlackNode *p);

void RbTreeDeleteAdjust(RBTree *T,RedBlackNode *parent,RedBlackNode *x);

void Output(RedBlackNode *p);

void PreorderTraverse(RedBlackNode *T);

void InorderTraverse(RedBlackNode *T);

void PostorderTraverse(RedBlackNode *T);

int prerecursion(RedBlackNode *T);

{

LinkStack *L;

Status StackEmpty(LinkStack *L)

if(L->next)

{

{

Status DestroyStack(LinkStack *L)

{

LinkStack *p,*r,*q;

p=L->next;

r=L;

if(p==NULL)

{

return FALSE;

}

while(p!=NULL)

{

r->next=p->next;

q=p;

p=p->next;

free(q);

}

free(L);

return TRUE;

LinkStack *p;

if(L==NULL)

{

i++;

p=p->next;

return i;

}

LinkStack *p;

{

p=p->next;

}

q=p->next->rbtree;

p->next=NULL;

return q;

}

Status PushStack(LinkStack *L,RedBlackNode *r)

{

LinkStack *p,*stacknode=(LinkStack*)malloc(sizeof(LinkStack));

p=L;

while(p->next!=NULL)

{

p=p->next;

}

stacknode->rbtree=r;

stacknode->next=NULL;

p->next=stacknode;

RedBlackNode *RBserach(RBTree *rbtree,int key) //查找值为 key 的节点

RedBlackNode *T;

while(T!=NULL&&T->data!=key)

{

else

{

}

}

RedBlackNode *RBMinimum(RBTree *T) //返回红黑树局部最小值

curNode=*T;

targetNode=NULL;

if(curNode!=NULL)

{

targetNode=curNode;

curNode=curNode->left;

}

return targetNode;

}