当前位置 : 主页 > 编程语言 > c语言 >

数据结构-->二叉树 OJ_01

来源:互联网 收集:自由互联 发布时间:2023-09-07
经过前几期浴血奋战!!二叉树便要进入应用阶段了!今天,为大家带来几道 OJ 题的讲解! 1.单值二叉树 如果二叉树每个结点都具有相同的值,那么该二叉树就是单值二叉树 只有给定

经过前几期浴血奋战!!二叉树便要进入应用阶段了!今天,为大家带来几道 OJ 题的讲解!

数据结构-->二叉树 OJ_01_布尔判断 相同的二叉树

1.单值二叉树

如果二叉树每个结点都具有相同的值,那么该二叉树就是单值二叉树

只有给定的树是单值二叉树时, 才会返回 true, 否则返回 false

下面为了方便理解,进行图解举例 :>

数据结构-->二叉树 OJ_01_单值二叉树_02

有上述的两种情况,其中还需要考虑到空节点的情况

现在上手代码,如下 :>

typedef int BTDataType;

typedef struct BinaryTree
{
	BTDataType data;
  struct BinaryTree* left;
  struct BinaryTree* right;
}BTNode;


//布尔判断单值二叉树
bool isUniverTree(BTNode* root)
{
	if(root == NULL)
    return true;
  
  if(root ->left && root ->left ->data != root ->data)
  {
  	return false;
  }
  
  if(root ->right && root ->right ->data != root ->data)
  {
  	return false;
  }
  
  return isUniverTree(root ->left) && isUniverTree(root ->right);
}

为了方便大家,能有更好的观感体验,特附上有色彩图样代码 :>

数据结构-->二叉树 OJ_01_布尔判断 相同的二叉树_03

另外,多讲一句废话!!上述代码,依靠强大的递归实现!!对递归是有要求的!!

2.相同的树

给定两颗二叉树的根结点 p 和 q, 编写一个函数来检验这两棵树是否相同!

如果两棵树在结构上相同,并且结点具有相同的值,则认为这两棵树相同!

本道 OJ 题,思路该如何打开呢?

-----> 既然是根结点,那么不可避免的是空结点的考虑!

下一步,则是存在根结点至少有一个不为空,那么言外之意是,有可能该两个根结点都不为空

此种情况的对应,是下列代码的,第二个 条件判断句,以及第三个 条件判断句

现在手搓代码 :>

typedef int BTDataType;

typedef struct BinaryTree
{
	BTDataType data;
  struct BinaryTree* left;
  struct BinaryTree* right;
}BTNode;

//布尔判断相同二叉树
bool isSameTree(BTNode* p, BTNode* q)
{
	if(p == NULL && q == NULL)
  {
		return true;  	
  }
  
  //至少有一个不为空
  if(p == NULL || q == NULL)
  {
  	return false;
  }
  
  //两个根结点都不为空
  if(p ->data != q ->data)
  {
  	return false;
  }
  
  //左子树递归遍历 && 右子树递归遍历
  return isSameTree(p ->left, q ->left)
    		&& isSameTree(p ->right, q ->right);
}

为了方便大家观感,特别附上彩色代码图样 :>

数据结构-->二叉树 OJ_01_单值二叉树_04

另外,注意一点,可能会有部分老友,对上述的解析看不懂

比如说,根结点的情况,当递归遍历的时候,从那个起始点开始,就当做了根结点!!

不知这样解说,是否已经足够清晰了!!

上一篇:自定义数据类型
下一篇:没有了
网友评论