用C语言编写算法判断两棵二叉树T和T’是否相似。两棵二叉树相似是指它们具有相同结构
时间: 2024-03-24 17:36:21 浏览: 11
可以按照以下步骤用C语言编写算法来判断两棵二叉树T和T'是否相似:
1. 定义二叉树结点的结构体,包括结点值、左子树、右子树等成员。
```
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
2. 编写递归函数 `isSimilar`,该函数判断两棵二叉树是否相似。若当前结点为空,则返回两棵树是否都为空的结果。若当前结点不为空,则判断两棵树的左右子树是否相似,若都相似,则返回 true,否则返回 false。
```
bool isSimilar(TreeNode* p, TreeNode* q) {
if (!p && !q) { // 两棵树都为空
return true;
}
if (!p || !q) { // 一棵树为空
return false;
}
if (p->val != q->val) { // 结点值不同
return false;
}
bool leftSimilar = isSimilar(p->left, q->left); // 左子树相似
bool rightSimilar = isSimilar(p->right, q->right); // 右子树相似
return leftSimilar && rightSimilar;
}
```
3. 在主函数中调用 `isSimilar` 函数,判断两棵二叉树是否相似。
```
int main() {
// 构造两棵二叉树
TreeNode* T = new TreeNode{1, new TreeNode{2, nullptr, nullptr}, new TreeNode{3, nullptr, nullptr}};
TreeNode* T1 = new TreeNode{1, new TreeNode{2, nullptr, nullptr}, new TreeNode{3, nullptr, nullptr}};
TreeNode* T2 = new TreeNode{1, new TreeNode{2, nullptr, nullptr}, new TreeNode{4, nullptr, nullptr}};
// 判断两棵二叉树是否相似
if (isSimilar(T, T1)) {
printf("T and T1 are similar.\n");
} else {
printf("T and T1 are not similar.\n");
}
if (isSimilar(T, T2)) {
printf("T and T2 are similar.\n");
} else {
printf("T and T2 are not similar.\n");
}
return 0;
}
```
以上是判断两棵二叉树是否相似的C语言算法实现。