C++以二叉链表作为二叉树的存储结构,编写以下算法: 1.统计二叉树的叶结点个数。 2.判别两棵树是否相等。 3.交换二叉树每个结点的左孩子和右孩子。 4.设计二叉树的双序遍历算法。
时间: 2024-04-30 11:22:04 浏览: 16
1. 统计二叉树的叶结点个数
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int countLeafNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
```
2. 判别两棵树是否相等
```c++
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
if (p == nullptr || q == nullptr) {
return false;
}
if (p->val != q->val) {
return false;
}
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
```
3. 交换二叉树每个结点的左孩子和右孩子
```c++
void swapLeftRight(TreeNode* root) {
if (root == nullptr) {
return;
}
swap(root->left, root->right);
swapLeftRight(root->left);
swapLeftRight(root->right);
}
```
4. 设计二叉树的双序遍历算法
```c++
void doubleOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " "; // 访问根节点
doubleOrderTraversal(root->left); // 访问左子树
cout << root->val << " "; // 访问根节点
doubleOrderTraversal(root->right); // 访问右子树
}
```