以二叉链表作为二叉树的存储结构,编写以下算法: (1)统计二叉树的叶结点个数。 (2)判断两棵树是否相等。 (3)交换二叉树每个结点的左孩子和右孩子。
时间: 2023-11-15 13:04:34 浏览: 146
好的,让我来一一回答你的问题:
1. 统计二叉树的叶节点个数的算法:
对于一棵二叉树,如果它是一棵空树,那么它的叶节点个数为0;如果它不是一棵空树,那么它的叶节点数等于它左子树的叶节点数加上它右子树的叶节点数。因此,一个递归的解决方案如下:
```
int countLeaves(BinaryTree *root) {
if (root == NULL) {
return 0;
} else if (root->left == NULL && root->right == NULL) {
return 1;
} else {
return countLeaves(root->left) + countLeaves(root->right);
}
}
```
2. 判断两棵树是否相等的算法:
对于两棵树的相等判断,我们要判断它们的根节点是否相等,以及它们的左子树和右子树是否相等。因此,一个递归的解决方案如下:
```
bool isEqual(BinaryTree *p, BinaryTree *q) {
if (p == NULL && q == NULL) {
return true;
} else if (p == NULL || q == NULL) {
return false;
} else if (p->val != q->val) {
return false;
} else {
return isEqual(p->left, q->left) && isEqual(p->right, q->right);
}
}
```
3. 交换二叉树每个节点的左孩子和右孩子的算法:
对于一棵二叉树,如果它是一棵空树,那么直接返回;否则,交换它的左孩子和右孩子,然后递归地对它的左子树和右子树进行交换操作。因此,一个递归的解决方案如下:
```
void swapChildren(BinaryTree *root) {
if (root == NULL) {
return;
}
BinaryTree *tmp = root->left;
root->left = root->right;
root->right = tmp;
swapChildren(root->left);
swapChildren(root->right);
}
```
希望这些算法能对你有所帮助!
阅读全文