设计一个算法,判别两棵二叉树是否相等。
时间: 2023-06-20 22:03:43 浏览: 60
可以通过递归的方式来判断两棵二叉树是否相等,具体步骤如下:
1. 如果两个二叉树都为空,返回true。
2. 如果两个二叉树中有一个为空,返回false。
3. 如果两个二叉树的根节点的值不相等,返回false。
4. 递归判断两个二叉树的左子树和右子树是否相等,如果都相等,返回true;否则返回false。
下面是一个示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
elif not p or not q:
return False
elif p.val != q.val:
return False
else:
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
```
其中,TreeNode 是二叉树节点的定义,is_same_tree 函数接收两个二叉树的根节点,返回是否相等的布尔值。
相关问题
设计一个C语言算法,判别两棵二叉树是否相等。
以下是一个递归的算法,用于判断两棵二叉树是否相等。
```c
#include <stdio.h>
#include <stdlib.h>
/* 定义二叉树结构体 */
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
/* 判断两棵二叉树是否相等 */
bool isSameTree(TreeNode* p, TreeNode* q) {
/* 如果两棵树都为空,则相等 */
if (p == NULL && q == NULL) {
return true;
}
/* 如果只有一棵树为空,则不相等 */
if (p == NULL || q == NULL) {
return false;
}
/* 如果根节点不相等,则不相等 */
if (p->val != q->val) {
return false;
}
/* 递归判断左右子树是否相等 */
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
/* 创建二叉树 */
TreeNode* createTree(int* nums, int n, int index) {
if (index >= n || nums[index] == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = nums[index];
root->left = createTree(nums, n, index * 2 + 1);
root->right = createTree(nums, n, index * 2 + 2);
return root;
}
/* 测试 */
int main() {
int nums1[] = {1, 2, 3};
int nums2[] = {1, 2, 3};
TreeNode* p = createTree(nums1, 3, 0);
TreeNode* q = createTree(nums2, 3, 0);
if (isSameTree(p, q)) {
printf("两棵二叉树相等\n");
} else {
printf("两棵二叉树不相等\n");
}
return 0;
}
```
以上代码中,`isSameTree`函数用于判断两棵二叉树是否相等。如果两棵树都为空,则它们相等;如果只有一棵树为空,则它们不相等;如果根节点不相等,则它们不相等;否则,递归判断左右子树是否相等。`createTree`函数用于创建二叉树,其中`-1`表示空节点。`main`函数用于测试,创建两棵相同的二叉树,并判断它们是否相等。
以二叉链表作为二叉树的存储结构,使用c++编写判别两棵树是否相等的算法。
二叉树的二叉链表存储结构定义如下:
```c
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
```
其中,`data`表示节点的数据,`lchild`和`rchild`分别指向节点的左子树和右子树。
判断两棵二叉树是否相等的算法如下:
```c
int isSameTree(BiTree p, BiTree q) {
if (p == NULL && q == NULL) { // 两棵树均为空,相等
return 1;
} else if (p == NULL || q == NULL) { // 一棵树为空,不相等
return 0;
} else if (p->data != q->data) { // 数据不相等,不相等
return 0;
} else { // 递归判断左子树和右子树
return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
}
}
```
首先判断两棵树是否均为空,若均为空,则两棵树相等;若一棵树为空,则两棵树不相等。若两棵树均不为空,但数据不相等,则两棵树不相等。若两棵树数据相等,则递归判断左子树和右子树是否相等。
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
BiTree createTree()
{
int data;
scanf("%d", &data);
if (data == -1) {
return NULL;
} else {
BiTree root = (BiTree)malloc(sizeof(BiTNode));
root->data = data;
root->lchild = createTree();
root->rchild = createTree();
return root;
}
}
int isSameTree(BiTree p, BiTree q) {
if (p == NULL && q == NULL) {
return 1;
} else if (p == NULL || q == NULL) {
return 0;
} else if (p->data != q->data) {
return 0;
} else {
return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
}
}
int main()
{
BiTree p = createTree();
BiTree q = createTree();
if (isSameTree(p, q)) {
printf("Two trees are same.\n");
} else {
printf("Two trees are not same.\n");
}
return 0;
}
```