【資料結構】二元樹練習

比較兩棵二元樹是否相等?



boolean  equal (  TreePtr  s  ,t)
{
if ( s == NULL &&  t == NULL  )
return true;
else if (s==NULL  ||  t==NULL)
return false;
else

return s->data  ==  t->data  && equal( s->  left , t->left)  &&  equal(s-> right  , t ->right);
}



計算二元樹的總節點數
int nodes ( TreePtr  t)
{
if (t==NULL) return 0;
else return nodes(t->left) + nodes(t->right)+1;
}

計算二元樹高度

int height  (TreePtr  t)
{
if (t==NULL
return 0;
else
return max (height(t->left),height(t->right))+1;
}

計算二元樹的Leaf數

int leaves (TreePtr t)
{
if (t==NULL)
return 0;
else
return max (leaves(t-> left) +leaves(t->right), 1);
}

●不使用max函數的作法
else
{
int x=leaves(t->left)
int y=leaves(t->right)
return (x+y ==0?  1:x+y);
}
◎時間複雜度=二元樹追蹤情況，共2n+1次呼叫，為O(n)