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

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

/*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法
经调试可运行源码及分析如下:
***/
#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    d
c     e  f
       g
a b c # # # d # # 如下:
    a
  b    d
c
a b c # # # x # # 如下:
    a
  b    x
c
*/

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

(0)

相关推荐

  • C++基于递归和非递归算法求二叉树镜像的方法

    本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

  • C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

    本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/

  • C++递归算法实例代码

    递归算法,总结起来具有以下几个特点: 特点1  它有一个基本部分,即直接满足条件,输出     特点2  它有一个递归部分,即 通过改变基数(即n),来逐步使得n满足基本部分的条件,从而输出     特点3  在实现的过程中,它采用了分治法的思想:        即将整体分割成部分,并总是从最小的部分(基本部分)开始入手(输出),其背后的原理在于 当整体递归到部分时,会保留整体的信息,部分满足条件输出的结果会被回溯给整体使用,从而使得整体输出结果.     特点4  每一步操作,整体都会将部分当

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

    本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同.分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二

  • Python基于递归和非递归算法求两个数最大公约数、最小公倍数示例

    本文实例讲述了Python基于递归和非递归算法求两个数最大公约数.最小公倍数.分享给大家供大家参考,具体如下: 最大公约数和最小公倍数的概念大家都很熟悉了,在这里就不多说了,今天这个是因为做题的时候遇到了所以就写下来作为记录,也希望帮到别人,下面是代码: #!/usr/bin/env python #coding:utf-8 from fractions import gcd #非递归实现 def gcd_test_one(a, b): if a!=0 and b!=0: if a>b: a,

  • Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

    本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(

  • Java编程二项分布的递归和非递归实现代码实例

    本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k

  • 分析python动态规划的递归、非递归实现

    概要 本文只是简单的介绍动态规划递归.非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar

  • Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例

    本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积.分享给大家供大家参考,具体如下: 什么是笛卡尔积? 在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员. 假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}. 如何用程序算法实现笛卡尔积? 如果编程前已知集合的数量

  • PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

  • 二叉树先序遍历的非递归算法具体实现

    在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)while,循环遍历当前结点,直至左孩子没有结点 3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1) 先看符合此思想的算法: 复制代码 代码如下: int PreOrderTraverseNonRecursiveEx(const BiTree &T, int

随机推荐