以二叉链表作为二叉树的存储结构,判别两棵树是否相等,给出相应的c++完整代码
时间: 2024-10-20 10:08:02 浏览: 22
在C++中,我们通常会通过深度优先搜索(DFS)或广度优先搜索(BFS)遍历二叉树,并比较节点及其值是否一一对应来判断两颗二叉链表表示的二叉树是否相等。这里是一个基于递归的DFS方法的示例:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 判断两个二叉树是否相等
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) {
return true; // 都为空,认为它们相等
}
if (p == NULL || q == NULL || p->val != q->val) {
return false; // 如果有一个为空或者值不匹配,返回false
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
int main() {
// 创建测试用例
TreeNode* tree1 = new TreeNode(1);
tree1->left = new TreeNode(2);
tree1->right = new TreeNode(3);
TreeNode* tree2 = new TreeNode(1);
tree2->left = new TreeNode(2);
tree2->right = new TreeNode(3);
// 检查是否相等
bool result = isSameTree(tree1, tree2);
cout << "The two binary trees are" << (result ? "" : " not") << "equal.\n";
return 0;
}
```
阅读全文