主题：求助：关于三色二叉树的问题
qinqinqin
[专家分：0] 发布于 2014-07-12 14:02:00
对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。
#include <iostream>
#include <string>
#include <stdlib.h>
#define DISABLE -2
#define RED 1
#define GREEN 2
#define BLUE 3
#define NOCOLOR 0
typedef struct bitnode
{
int color;
struct bitnode *
lchild,*rchild,*fathernode,*prenode;
}bitnode,*BITree;
BITree prenode=NULL;
using namespace std;
int curpos=0,sonstr=0;
int *toint;
int ball_color[3];
string convert;
void outputmaxmin()
{ int
回复列表 （共1个回复）
沙发
qinqinqin [专家分：0] 发布于 2014-07-12 14:03:00
max=ball_color[0]>ball_color[1]?(ball_color[0]>ball_color[2]?ball_color[0]:ball_color[2]):
(ball_color[1]>ball_color[2]?ball_color[1]:ball_color[2]);
cout<color-1]++;
computecolornode(temp_tree->lchild);
computecolornode(temp_tree->rchild);
}
}
void colornode(BITree&temp_tree)
{
if(temp_tree)
{
if(temp_tree->fathernode==NULL)
{
temp_tree->color=RED;
}
else
if(temp_tree->fathernode->lchild==temp_tree||temp_tree->fathernode->lchild==NULL)
{
if(temp_tree->fathernode->color==RED)
temp_tree->color=GREEN;
if(temp_tree->fathernode->color==GREEN)
temp_tree->color=RED;
if(temp_tree->fathernode->color==BLUE)
temp_tree->color=RED;
}
else
{
if(temp_tree->fathernode->color==RED&&temp_tree->fathernode->lchild->color==GREEN)
temp_tree->color=BLUE;
if(temp_tree->fathernode->color==BLUE&&temp_tree->fathernode->lchild->color==RED)
temp_tree->color=GREEN;
if(temp_tree->fathernode->color==GREEN&&temp_tree->fathernode->lchild->color==RED)
temp_tree->color=BLUE;
}
colornode(temp_tree->lchild);
colornode(temp_tree->rchild);
}
}
string inputnode()
{
return
convert.substr(sonstr++,1);
}
BITree xdd=NULL;
void constructbintree(BITree
&temp_tree,string temp)
{
if(!temp.compare("0"))
temp_tree=NULL;
else
{
temp_tree=(bitnode
*)malloc(sizeof(bitnode));
temp_tree->color=NOCOLOR;
temp_tree->prenode=prenode;
xdd=prenode;
if(xdd==NULL)
temp_tree->fathernode=NULL;
else
{
while(xdd!=NULL)
{
if(xdd->lchild==temp_tree||xdd->rchild==temp_tree)
{
temp_tree->fathernode=xdd;
break;
}
xdd=xdd->prenode;
}
}
prenode=temp_tree;
constructbintree(temp_tree->lchild,inputnode());
constructbintree(temp_tree->rchild,inputnode());
}
return;
}
void makestring(int toint[],int
length,string &convert)
{
convert="1";
int * temp=new int[length];
int cur=0,var=0;
while(cur0)
{
convert+="1";
temp[cur]=toint[cur]-1;
}
if(toint[cur]==0)
{
convert+="00";
temp[cur]=DISABLE;
var=cur-1;
for(;var>=0;var--)
{
if(temp[var]!=DISABLE)
{
if(temp[var]==1)
{
convert+="1";
if(toint[var]==2)
{
temp[var]=DISABLE;
}
else
{
temp[var]--;
}
break;
}
else
{
convert+="0";
temp[var]=DISABLE;
}
}
}
}
cur++;
}
}
int main()
{
string seq;
BITree temp_tree;
cout<<"请输入二叉树序列"<>seq;
toint=new int[seq.length()];
for(int i=0;i
我来回复
您所在位置：