算法导论-红黑树C++实现 - c++编程基础

)
{
return node->Getkey();
}
bool Getcolor(BRTreeNode* node)
{
return node->Getcolor();
}
BRTreeNode* Getroot()
{
return root;
}
BRTreeNode* GetParent(BRTreeNode*node)
{
return node->parent;
}
int GetHeight(BRTreeNode* node)
{
int L,R;
if(node==nil)
return 0;
L=GetHeight(node->left);
R=GetHeight(node->right);
return 1+(L>R L:R);
}
int GetBlackHeight(BRTreeNode* node)
{
int L,R;
if(node==nil) return 0;
L=GetHeight(node->left);
R=GetHeight(node->right);
if(node->Getcolor()) return(L>R L:R);
else return 1+(L>R L:R);
}
void Inorder(BRTreeNode*node)
{
if(node!=nil)
{
Inorder(node->left);
cout<key<<" ";
Inorder(node->right);
}
}
void Preorder(BRTreeNode*node)
{
if(node!=nil)
{
cout<key<<" ";
Preorder(node->left);
Preorder(node->right);
}
}
void Posetorder(BRTreeNode*node)
{
if(node!=nil)
{
Posetorder(node->left);
Posetorder(node->right);
cout<key<<" ";
}
}
//层次法打印树
void DispTree(BRTreeNode*BT)
{
BRTreeNode stack[maxSize],p;
int level[maxSize][2],top,n,i,width=4;
if(BT!=NULL)
{
cout<<"Display a tree by hollow means."< top=1;
stack[top]=BT;//push root point to stack.
level[top][0]=width;
while(top>0)
{
p=stack[top];
n=level[top][0];
for(i=1;i<=n;i++)
cout<<" ";
//输出信息
if(p.key==0)
{
cout<<")";
}
else{
if(p.key==-1) cout<<"Nil";
else if(p.left&&p.right) cout<<"("< else cout< if(p.Getcolor()) cout<<"R,";
else cout<<"B,";
}
for(i=n+1;i cout<<"--";
cout<

top--;
if(p.right!=NULL)
{
//插入一个括号节点，key值为0
top++;
BRTreeNode* tmp=new BRTreeNode();
tmp->key=0;
stack[top]=tmp;
level[top][0]=n+width;
level[top][1]=2;
top++;
stack[top]=p.right;
level[top][0]=n+width;
level[top][1]=2;

}
if(p.left!=NULL)
{
top++;
stack[top]=p.left;
level[top][0]=n+width;
level[top][1]=1;
}
}
}
}
//左旋节点node
bool LeftRotate(BRTreeNode* node)
{
BRTreeNode*y;
if(node->right==nil)
{
cout<<"can't left rotate!"< return 0;
}
y=node->right;
node->right=y->left;
if(y->left!=nil)
{
y->left->parent=node;
}
y->parent=node->parent;
if(node->parent==nil)
{
root=y;
}
else if(node->parent->left==node)
{
node->parent->left=y;
}
else
{
node->parent->right=y;
}
y->left=node;
node->parent=y;
return 1;
}
//右旋节点
bool RightRotate(BRTreeNode* node)
{
if(node->left==nil)
{
cout<<"can't rightrotate!"< return 0;
}
BRTreeNode* x;
x=node->left;
node->left=x->right;
if(x->right!=nil)
{
x->right->parent=node;
}
x->parent=node->parent;
if(node->parent==nil)
{
root=x;
}
else if(node->parent->left==node)
{
node->parent->left=x;
}
else
{
node->parent->right=x;
}
node->parent=x;
x->right=node;
return 1;
}
void Insert(int num)
{
BRTreeNode* node=new BRTreeNode(num,1);
node->left=nil;
node->right=nil;

算法导论-红黑树C++实现 (六)