http://community.csdn.net/Expert/TopicView.asp?id=5305770
对，我也想到了这个算法。
就是scv120的算法。
我定义的插入元素的方法是：
curnode:当前在树中定位到的节点
inservalue:要插入的值
isleft:当前在树中定位到的节点是其父节点的左节点，还是右节点
issmall:当前在树中定位到的节点比其父节点大或小。
setItem(curnode,insertvalue,isleft,issmall)
{
if(curnode==NULL)
{
if(isleft)curnode=getnode(insertvalue);
elseif(notissmall)curnode=getnode(insertvalue);
}
else{
if(*curnode
#include
#include
#definetrue1
#definefalse0
structTreeNode{
intvalue;
structTreeNode*leftNode;
structTreeNode*rightNode;
intpathFlag;/*0:在得到最终线路时应往左下去1:在得到最终线路时应往右下去-1:终点*/
};
/*将一个值变为一个节点传出*/
structTreeNode*getNode(intvalue){
structTreeNode*treenode;
treenode=(structTreeNode*)malloc(sizeof(structTreeNode));
treenode->value=value;
treenode->leftNode=NULL;
treenode->rightNode=NULL;
returntreenode;
}
/*得到输入值*/
intgetinputValue(){
charstr[20];
printf("input:(结束：-1)\n");
gets(str);/*是获得字符串*/
returnatoi(str);/*strtoint*/
}
/*插入数据
curnode:当前在树中定位到的节点
inservalue:要插入的值
isleft:当前在树中定位到的节点是其父节点的左节点，还是右节点
issmall:当前在树中定位到的节点比其父节点大或小。
*/
voidinsertItem(structTreeNode**curnode,intinsertvalue,intisleft,intissmall)
{
if(*curnode==NULL)
{
if(isleft==true)*curnode=getNode(insertvalue);
elseif(issmall==false)*curnode=getNode(insertvalue);
}
else{
if(insertvaluevalue){
insertItem(&((*curnode)->leftNode),insertvalue,true,true);
insertItem(&((*curnode)->rightNode),insertvalue,false,true);
}
else{
insertItem(&((*curnode)->rightNode),insertvalue,false,false);
}
}
}
/*得到最终路线,返回路线的长度*/
intgetPath(structTreeNode*curnode){
intleftvalue;
intrightvalue;
intret;
if(curnode==NULL){
return-1;
}
printf("(");
leftvalue=getPath(curnode->leftNode);
printf("%d",curnode->value);
rightvalue=getPath(curnode->rightNode);
printf(")");
if(rightvalue==-1&&leftvalue==-1){
curnode->pathFlag=-1;
ret=1;
}
else{
if(leftvalue>=rightvalue){
curnode->pathFlag=0;
ret=leftvalue+1;
}
else{
curnode->pathFlag=1;
ret=rightvalue;
}
}
returnret;
}
/*将树中的最终链打印出来*/
putvalue(structTreeNode*curnode){
if(curnode->pathFlag==0){
printf("%d",curnode->value);
putvalue(curnode->leftNode);
}
elseif(curnode->pathFlag==1){
putvalue(curnode->rightNode);
}
else{
printf("%d",curnode->value);
}
}
int
main(){
intvalue;
structTreeNode*root=NULL;
while((value=getinputValue())!=-1){/*输入-1则退出输入*/
insertItem(&root,value,true,true);
}
printf("\n子串的长度:%d\n",getPath(root));
if(root!=NULL)
{
printf("得到的序列：");
putvalue(root);
}
printf("\n");
return0;
}
|
