C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同。分享给大家供大家参考，具体如下：

#include 
#include 
#include 
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);
  }
}


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);
}


bool bitree_compare_leveltraverse(BTreeNode* proot1, BTreeNode* proot2)
{
  if (proot1 == NULL && proot2 == NULL)//都为空
    return true;
  queue  que1;
  queue  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;
}

希望本文所述对大家C++程序设计有所帮助。