數(shù)據(jù)結(jié)構(gòu)

劉中鋒 · 發(fā)表于 2014-12-13 22:12

題目：輸入一個(gè)整數(shù)data和一棵二元樹，從樹的根節(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉節(jié)點(diǎn)，所經(jīng)過(guò)的所有節(jié)點(diǎn)形成一條路徑。打印出路徑的和與data相等的所有元素。

我的算法：看看對(duì)不對(duì)啊。

琴魂醉 · 發(fā)表于 2014-12-13 22:56

你寫的有問(wèn)題。這題用先序非遞歸比較簡(jiǎn)單。一旦找到路徑和等于data時(shí)，保留top，把棧中所有結(jié)點(diǎn)復(fù)制到另外一個(gè)棧，然后輸出

劉中鋒 · 發(fā)表于 2014-12-14 12:59

琴魂醉發(fā)表于 2014-12-13 22:56
你寫的有問(wèn)題。這題用先序非遞歸比較簡(jiǎn)單。一旦找到路徑和等于data時(shí)，保留top，把棧中所有結(jié)點(diǎn)復(fù)制到另外 ...

是嗎，王道上的題，它說(shuō)用遞歸

琴魂醉 · 發(fā)表于 2014-12-14 19:47

本帖最后由琴魂醉于 2014-12-14 20:06 編輯

劉中鋒發(fā)表于 2014-12-14 12:59
是嗎，王道上的題，它說(shuō)用遞歸

我只是說(shuō)非遞歸先序比較簡(jiǎn)單，沒(méi)說(shuō)遞歸不可以
typedef struct btnode
{
int data，flag=0;
struct btnode *lchild,*rchild;
}*BiTree,btnode;
void pre(BiTree bt,int datasum)//通過(guò)先序非遞歸,棧中保存的都是祖先結(jié)點(diǎn)
{
int top=0,sum=0,i;
BtTree s[],s1[],p=bt;//棧足夠大
while(p||top>0)
{
if(p)
{
   s[++top]=p;
   if(!p->lchild&&!p->rchild)//判斷是否是葉子結(jié)點(diǎn)
{
      sum=0;
      for(i=top;i>0;--i)//把棧中祖先結(jié)點(diǎn)復(fù)制到s1中
      {
      s1(i)=s (i);  //由于[]沒(méi)法顯示，我就是用（）當(dāng)做[]
      sum+=s (i)->data;
      }//endfor
      if(sum==datasum)
   {
         for(i=1;i<top;++i)//依次打印,即可從祖先結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)
      {
         printf("%d/t",s1 (i)->data);
      }//endfor
      }//endif
   }//endif
   p=p->lchild;//訪問(wèn)左孩子
}
else
{
p=s[top--];
p=p->rchild;
}
}//endwhile
}