《1》 编写函数bool isEqualTree(BiTNode *T1,BiTNode *T2) , 判别两颗二叉树是否相等
时间: 2024-02-22 13:00:07 浏览: 25
好的,我可以帮你编写判断两颗二叉树是否相等的函数。以下是C++代码实现:
```c++
bool isEqualTree(BiTNode *T1, BiTNode *T2) {
if (T1 == nullptr && T2 == nullptr) { // 两颗树均为空,返回true
return true;
}
if (T1 == nullptr || T2 == nullptr) { // 有一颗树为空,返回false
return false;
}
if (T1->data != T2->data) { // 根节点数据不相等,返回false
return false;
}
bool leftEqual = isEqualTree(T1->lchild, T2->lchild); // 递归判断左子树是否相等
bool rightEqual = isEqualTree(T1->rchild, T2->rchild); // 递归判断右子树是否相等
return leftEqual && rightEqual; // 左右子树均相等,返回true,否则返回false
}
```
该函数的思路是:若两颗树均为空,返回true;若有一颗树为空,返回false;若根节点数据不相等,返回false;否则递归判断左右子树是否相等。最终判断左右子树是否均相等,返回结果。
你可以将函数加入到你的代码中,并传入两颗二叉树的根节点进行测试。
相关问题
编写函数bool isEqualTree(BiTNode *T1,BiTNode *T2) , 判别两颗二叉树是否相等,并给出完整代码
好的,以下是完整的C++代码实现,包括二叉树的结构体和创建二叉树的函数:
```c++
#include <iostream>
using namespace std;
// 二叉树结点结构体
typedef struct BiTNode {
int data;
BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 创建二叉树
void createBiTree(BiTree &T) {
int data;
cin >> data;
if (data == 0) { // 输入0表示该节点为空
T = nullptr;
} else {
T = new BiTNode;
T->data = data;
createBiTree(T->lchild); // 递归创建左子树
createBiTree(T->rchild); // 递归创建右子树
}
}
// 判断两个二叉树是否相等
bool isEqualTree(BiTree T1, BiTree T2) {
if (T1 == nullptr && T2 == nullptr) { // 两颗树均为空,返回true
return true;
}
if (T1 == nullptr || T2 == nullptr) { // 有一颗树为空,返回false
return false;
}
if (T1->data != T2->data) { // 根节点数据不相等,返回false
return false;
}
bool leftEqual = isEqualTree(T1->lchild, T2->lchild); // 递归判断左子树是否相等
bool rightEqual = isEqualTree(T1->rchild, T2->rchild); // 递归判断右子树是否相等
return leftEqual && rightEqual; // 左右子树均相等,返回true,否则返回false
}
int main() {
BiTree T1, T2;
cout << "请输入第一颗二叉树(前序遍历,0表示空节点):" << endl;
createBiTree(T1);
cout << "请输入第二颗二叉树(前序遍历,0表示空节点):" << endl;
createBiTree(T2);
if (isEqualTree(T1, T2)) {
cout << "两颗二叉树相等" << endl;
} else {
cout << "两颗二叉树不相等" << endl;
}
return 0;
}
```
你可以将该代码复制到C++编译器中进行测试。
编写函数bool isCompleteTree(BiTNode *T),判断T是否为完全二叉树
完全二叉树的定义是:对于一棵具有n个结点的二叉树,如果其结点按层序编号(从1开始),对任一结点i(1<=i<=n):
1. 如果i=1,则结点i是二叉树的根结点,无双亲;如果i>1,则其双亲是结点i/2(下取整)。
2. 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
3. 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。
因此,判断一棵二叉树是否为完全二叉树,可以按照以下步骤进行:
1. 从根节点开始,按照层序遍历二叉树,将每个节点依次编号为1,2,3,...n。
2. 如果当前节点的编号为i,且其左孩子编号为j,右孩子编号为k,则有以下几种情况:
(1)如果j>n,说明当前节点已经是叶子节点,后面的节点都应该是叶子节点,否则不是完全二叉树。
(2)如果k>n,说明当前节点只有左孩子,后面的节点都应该没有孩子,否则不是完全二叉树。
(3)如果j<=n且k<=n,继续遍历。
3. 如果遍历完所有节点,都没有发现不符合上述规则的情况,则该二叉树是完全二叉树。
下面是判断完全二叉树的代码实现:
```c++
#include <queue>
#include <cmath>
using namespace std;
struct BiTNode {
int val;
BiTNode *left;
BiTNode *right;
BiTNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isCompleteTree(BiTNode *T) {
if (T == NULL) return true; // 空树是完全二叉树
queue<BiTNode*> q;
q.push(T);
int i = 1, n = 1; // i为当前节点编号,n为当前层总节点数
while (!q.empty()) {
int cnt = q.size(); // 当前层节点数
if (cnt != n) return false; // 不满足完全二叉树的条件
for (int j = 0; j < cnt; j++) {
BiTNode* node = q.front();
q.pop();
if (i != node->val) return false; // 不满足完全二叉树的条件
if (node->left != NULL) {
q.push(node->left);
if (2 * i > pow(2, floor(log2(n)) + 1)) return false; // 不满足完全二叉树的条件
}
if (node->right != NULL) {
q.push(node->right);
if (2 * i + 1 > pow(2, floor(log2(n)) + 1)) return false; // 不满足完全二叉树的条件
}
i++;
}
n *= 2;
}
return true;
}
```
其中,floor(log2(n))表示n的二进制位数减1,即层数。pow(2, floor(log2(n)) + 1)表示当前层的最大节点编号。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)