//層次遍歷法判斷兩棵樹(shù)是否相似
bool IsSemblable1(BiTree T1,BiTree T2)
{
  stack<BiTNode* > _sta1,_sta2;  //用來(lái)存放下一層元素的容器，此處棧和隊(duì)列都行
  BiTNode *p1 = T1,*p2 = T2;   //p1用來(lái)跟蹤T1,p2用來(lái)跟蹤T2
  while((_sta1.empty() == false || p1 != NULL) &&(_sta2.empty() == false || p2 != NULL))
  {
    if(p1 != NULL && p2 != NULL )  //如果p1和p2都不為空時(shí)
    {
      if(p1->lchild != NULL && p2->lchild != NULL)  //如果p1和p2的左子樹(shù)都不為空時(shí)
      {
        _sta1.push(p1->lchild);
        _sta2.push(p2->lchild);
      }
      else if( p1->lchild != NULL || p2->lchild != NULL)  //如果p1的左子樹(shù)為空，但是p2的左子樹(shù)不為空，或者相反
        return false;
      if(p1->rchild != NULL && p2->rchild != NULL)   //如果p1和p2的右子樹(shù)都不為空時(shí)
      {
        _sta1.push(p1->rchild);
        _sta2.push(p2->rchild);
      }
      else if(p1->rchild != NULL || p2->rchild != NULL)  //如果p1的右子樹(shù)為空，但是p2的右子樹(shù)不為空，或者相反
        return false;
      //訪問(wèn)完兩棵樹(shù)的當(dāng)前結(jié)點(diǎn)后，置空讓下一次循環(huán)彈出棧中元素（此處其實(shí)直接彈出元素也行）
      p1 = NULL;
      p2 = NULL;
    }
    else if(p1 != NULL || p2 != NULL)    //當(dāng)前節(jié)點(diǎn)有一個(gè)為空
      return false;
    else
    {
      //彈出兩個(gè)樹(shù)的棧頂元素
      p1 = _sta1.top();
      p2 = _sta2.top();
      _sta1.pop();
      _sta2.pop();
    }
  }
  return true;
}

//遞歸判斷兩棵樹(shù)是否相似
bool IsSemblable2(BiTree T1,BiTree T2)
{
  bool leftS = false,rightS = false;   //用來(lái)接受子樹(shù)返回的信息
  if(T1 == NULL && T2 == NULL)    //兩個(gè)結(jié)點(diǎn)都為空
    return true;
  else if(T1 == NULL || T2 == NULL)  //有一個(gè)結(jié)點(diǎn)不為空
    return false;
  else
  {
    int leftS = IsSemblable2(T1->lchild,T2->lchild);  //遞歸左子樹(shù)
    int rightS = IsSemblable2(T1->rchild,T2->rchild);  //遞歸右子樹(shù)
    return leftS && rightS ;  //返回兩個(gè)子樹(shù)的信息
  }
}