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

>MakeEmpty();
delete this;
}
}
int GetHeight()
{
int L,R;
if(this==NULL)
{
return 0;
}
L=this->left->GetHeight();
R=this->right->GetHeight();
return 1+(L>R L:R);
}
};

#endif // BRTREENODE_H_INCLUDED

BRTree.h

[cpp]
#ifndef BRTREE_H_INCLUDED
#define BRTREE_H_INCLUDED
#define maxSize 30
#define maxWidth 30
#include"BRTreeNode.h"
class BRTree
{
private:
BRTreeNode* root;
BRTreeNode* nil;
public:
BRTree():nil(new BRTreeNode())
{
nil->color=0;
nil->key=-1;
nil->left=nil->right=nil->parent=NULL;
root=nil;
}
~BRTree()
{
MakeEmpty(root);
delete nil;
}
//清空以node为根节点的树
void MakeEmpty(BRTreeNode*node)
{
if(node!=nil)
{
MakeEmpty(node->left);
MakeEmpty(node->right);
delete node;
}
}
int Getkey(BRTreeNode* node)
{
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++;
st

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