數據結構

劉中鋒 · 發表于 2014-12-13 22:12

題目：輸入一個整數data和一棵二元樹，從樹的根節點開始往下訪問一直到葉節點，所經過的所有節點形成一條路徑。打印出路徑的和與data相等的所有元素。

我的算法：看看對不對啊。

琴魂醉 · 發表于 2014-12-13 22:56

你寫的有問題。這題用先序非遞歸比較簡單。一旦找到路徑和等于data時，保留top，把棧中所有結點復制到另外一個棧，然后輸出

劉中鋒 · 發表于 2014-12-14 12:59

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

是嗎，王道上的題，它說用遞歸

琴魂醉 · 發表于 2014-12-14 19:47

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

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

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