/*兩個二叉樹結構是否相同(結構和數據都相同) -- 遞歸和非遞歸方法經調試可運行源碼及分析如下：***/#include <stdlib.h>#include <iostream>#include <queue>using std::cout;using std::cin;using std::endl;using std::queue;/*二叉樹結點定義*/typedef struct BTreeNode{  char elem;  struct BTreeNode *pleft;  struct BTreeNode *pright;}BTreeNode;/*初始化二叉樹節點*/BTreeNode* btree_init(BTreeNode* &bt){  bt = NULL;  return bt;}/*先序創建二叉樹*/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);  }}/*遞歸方式:如果兩個二叉樹proot都為空樹，則自然相同，返回true；如果兩個二叉樹proot一個為空樹，另一個不為空樹，則不相同，返回false；如果兩個二叉樹的數據不相等，返回false;如果兩個二叉樹都不為空樹，則需要分別比較左右子樹后，根據比較結果共同判定，只要有一個為false，則返回false。*//*遞歸判斷兩個二叉樹是否相等(結構和數據)*/bool bitree_compare(BTreeNode* proot1, BTreeNode* proot2){  if (proot1 == NULL && proot2 == NULL)//都為空    return true;  if((proot1 != NULL && proot2 == NULL) ||    (proot1 == NULL && proot2 != NULL))//一個空，一個非空    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);}/*非遞歸方式借助隊列實現實現算法：首先將給定根節點proot1和proot2都入隊第一步：當兩個隊列未空時，分別獲取兩個樹的當前層次中節點總數（即當前隊列中節點個數），    先比較節點個數是否相同，如果不相同，則兩個樹自然不同；    如果節點個數相同，需要出隊進行比較(數據也要比較)。如果有一個隊列未空，則退出比較。第二步：如果有一個隊列未空，則清空隊列并返回不同。*//*非遞歸方式判斷兩個二叉樹是否相等（僅僅結構）*/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();    //節點數目不一樣時flag設為false，退出循環    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();      /*元素數據比較*/      if(proot1->elem != proot2->elem)      {        flag = false;        break;      }      //判斷左右孩子是否相同，不同肯定結構不相同，提前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;      }      /*下一層的節點入隊*/      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);//初始化根節點  btree_init(bt2);//初始化根節點  cout << "creat 1th tree:" << endl;  pre_crt_tree(bt1);//創建二叉樹  cout << "creat 2th tree:" << endl;  pre_crt_tree(bt2);//創建二叉樹  /*遞歸測試*/  flag = bitree_compare(bt1, bt2);  if(flag == true)    cout<< "遞歸：result is true." << endl;  else    cout << "遞歸：result is false." << endl;  /*非遞歸測試*/  bitree_compare_leveltraverse(bt1, bt2);  system("pause");  return 0;}

/*測試結果如下：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.請按任意鍵繼續. . .------------------分界線-----------------------creat 1th tree:a b c # # # d # #creat 2th tree:a b c # # # x # #遞歸：result is false.非遞歸：reslut is false.請按任意鍵繼續. . .本例創建的二叉樹形狀：a b c # # # d e # # f # g # # 如下：    a  b    dc     e  f       ga b c # # # d # # 如下：    a  b    dca b c # # # x # # 如下：    a  b    xc*/