/*兩個(gè)二叉樹結(jié)構(gòu)是否相同(結(jié)構(gòu)和數(shù)據(jù)都相同) -- 遞歸和非遞歸方法
經(jīng)調(diào)試可運(yùn)行源碼及分析如下：
***/
#include <stdlib.h>
#include <iostream>
#include <queue>
using std::cout;
using std::cin;
using std::endl;
using std::queue;
/*二叉樹結(jié)點(diǎn)定義*/
typedef struct BTreeNode
{
  char elem;
  struct BTreeNode *pleft;
  struct BTreeNode *pright;
}BTreeNode;
/*初始化二叉樹節(jié)點(diǎn)*/
BTreeNode* btree_init(BTreeNode* &bt)
{
  bt = NULL;
  return bt;
}
/*先序創(chuàng)建二叉樹*/
void pre_crt_tree(BTreeNode* &bt)
{
  char ch;
  cin >> ch;
  if (ch == '#')
  {
    bt = NULL;
  }
  else
  {
    bt = new BTreeNode;
    bt->elem = ch;
    pre_crt_tree(bt->pleft);
    pre_crt_tree(bt->pright);
  }
}
/*
遞歸方式:
如果兩個(gè)二叉樹proot都為空樹，則自然相同，返回true；
如果兩個(gè)二叉樹proot一個(gè)為空樹，另一個(gè)不為空樹，則不相同，返回false；
如果兩個(gè)二叉樹的數(shù)據(jù)不相等，返回false;
如果兩個(gè)二叉樹都不為空樹，則需要分別比較左右子樹后，根據(jù)比較結(jié)果共同判定，只要有一個(gè)為false，則返回false。
*/
/*遞歸判斷兩個(gè)二叉樹是否相等(結(jié)構(gòu)和數(shù)據(jù))*/
bool bitree_compare(BTreeNode* proot1, BTreeNode* proot2)
{
  if (proot1 == NULL && proot2 == NULL)//都為空
    return true;
  if((proot1 != NULL && proot2 == NULL) ||
    (proot1 == NULL && proot2 != NULL))//一個(gè)空，一個(gè)非空
    return false;
  /*比較元素*/
  if(proot1->elem != proot2->elem)
    return false;
  bool left_compare = bitree_compare(proot1->pleft, proot2->pleft);
  bool right_compare = bitree_compare(proot1->pright, proot2->pright);
  return (left_compare && right_compare);
}
/*
非遞歸方式
借助隊(duì)列實(shí)現(xiàn)
實(shí)現(xiàn)算法：
首先將給定根節(jié)點(diǎn)proot1和proot2都入隊(duì)
第一步：當(dāng)兩個(gè)隊(duì)列未空時(shí)，分別獲取兩個(gè)樹的當(dāng)前層次中節(jié)點(diǎn)總數(shù)（即當(dāng)前隊(duì)列中節(jié)點(diǎn)個(gè)數(shù)），
    先比較節(jié)點(diǎn)個(gè)數(shù)是否相同，如果不相同，則兩個(gè)樹自然不同；
    如果節(jié)點(diǎn)個(gè)數(shù)相同，需要出隊(duì)進(jìn)行比較(數(shù)據(jù)也要比較)。如果有一個(gè)隊(duì)列未空，則退出比較。
第二步：如果有一個(gè)隊(duì)列未空，則清空隊(duì)列并返回不同。
*/
/*非遞歸方式判斷兩個(gè)二叉樹是否相等（僅僅結(jié)構(gòu)）*/
bool bitree_compare_leveltraverse(BTreeNode* proot1, BTreeNode* proot2)
{
  if (proot1 == NULL && proot2 == NULL)//都為空
    return true;
  queue <BTreeNode*> que1;
  queue <BTreeNode*> que2;
  que1.push(proot1);
  que2.push(proot2);
  int cur_level_nodes_num1 = 0;
  int cur_level_nodes_num2 = 0;
  bool flag = true;
  while (!que1.empty() && !que2.empty())
  {
    cur_level_nodes_num1 = que1.size();
    cur_level_nodes_num2 = que2.size();
    //節(jié)點(diǎn)數(shù)目不一樣時(shí)flag設(shè)為false，退出循環(huán)
    if (cur_level_nodes_num1 != cur_level_nodes_num2)
    {
      flag = false;
      break;
    }
    int cur_level_node_count1 = 0;
    int cur_level_node_count2 = 0;
    while (cur_level_node_count1 < cur_level_nodes_num1 &&
        cur_level_node_count2 < cur_level_nodes_num2)
    {
      ++cur_level_node_count1;
      ++cur_level_node_count2;
      proot1 = que1.front();
      que1.pop();
      proot2 = que2.front();
      que2.pop();
      /*元素?cái)?shù)據(jù)比較*/
      if(proot1->elem != proot2->elem)
      {
        flag = false;
        break;
      }
      //判斷左右孩子是否相同，不同肯定結(jié)構(gòu)不相同，提前break
      if( proot1->pleft == NULL && proot2->pleft != NULL  ||
        proot1->pleft != NULL && proot2->pleft == NULL  ||
        proot1->pright == NULL && proot2->pright != NULL ||
        proot1->pright != NULL && proot2->pright == NULL)
      {
        flag = false;
        break;
      }
      /*下一層的節(jié)點(diǎn)入隊(duì)*/
      if(proot1->pleft)
        que1.push(proot1->pleft);
      if(proot1->pright)
        que1.push(proot1->pright);
      if(proot2->pleft)
        que2.push(proot2->pleft);
      if(proot2->pright)
        que2.push(proot2->pright);
    }
    if(flag == false)
      break;
  }
  if(flag == false)
  {
    while(!que1.empty())
      que1.pop();
    while(!que2.empty())
      que2.pop();
    cout << "非遞歸：reslut is false." << endl;
    return false;
  }else
  {
    cout << "非遞歸：reslut is true." << endl;
    return true;
  }
  return true;
}
int main()
{
  BTreeNode *bt1;
  BTreeNode* bt2;
  bool flag;
  btree_init(bt1);//初始化根節(jié)點(diǎn)
  btree_init(bt2);//初始化根節(jié)點(diǎn)
  cout << "creat 1th tree:" << endl;
  pre_crt_tree(bt1);//創(chuàng)建二叉樹
  cout << "creat 2th tree:" << endl;
  pre_crt_tree(bt2);//創(chuàng)建二叉樹
  /*遞歸測(cè)試*/
  flag = bitree_compare(bt1, bt2);
  if(flag == true)
    cout<< "遞歸：result is true." << endl;
  else
    cout << "遞歸：result is false." << endl;
  /*非遞歸測(cè)試*/
  bitree_compare_leveltraverse(bt1, bt2);
  system("pause");
  return 0;
}

/*
測(cè)試結(jié)果如下：
creat 1th tree:
a b c # # # d e # # f # g # #
creat 2th tree:
a b c # # # d e # # f # g # #
遞歸：result is true.
非遞歸：reslut is true.
請(qǐng)按任意鍵繼續(xù). . .
------------------分界線-----------------------
creat 1th tree:
a b c # # # d # #
creat 2th tree:
a b c # # # x # #
遞歸：result is false.
非遞歸：reslut is false.
請(qǐng)按任意鍵繼續(xù). . .
本例創(chuàng)建的二叉樹形狀：
a b c # # # d e # # f # g # # 如下：
    a
  b    d
c     e  f
       g
a b c # # # d # # 如下：
    a
  b    d
c
a b c # # # x # # 如下：
    a
  b    x
c
*/