编写程序实现求二叉树的结点个数,叶结点个数,二叉树的高度及交换二叉树所有左右子树的操作
时间: 2024-11-21 12:22:36 浏览: 23
要编写程序实现二叉树的节点计数、叶节点计数、高度计算以及交换子树的操作,可以使用递归的方式来进行。下面是相关的代码实现:
### 1. 求二叉树的节点数
```cpp
int countNodes(TreeNode* node) {
if (node == nullptr) {
return 0;
}
return 1 + countNodes(node->left) + countNodes(node->right);
}
// 示例:
TreeNode* root; // 树的根节点
cout << "Total nodes: " << countNodes(root) << endl;
```
### 2. 求二叉树的叶节点数
```cpp
int countLeaves(TreeNode* node) {
if (node == nullptr || (node->left == nullptr && node->right == nullptr)) {
return 1;
}
return countLeaves(node->left) + countLeaves(node->right);
}
// 示例:
cout << "Total leaves: " << countLeaves(root) << endl;
```
### 3. 求二叉树的高度(这里假设二叉树是平衡的,对于非平衡的树,需要采用其他复杂算法如Kahn算法)
```cpp
int height(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int leftHeight = height(node->left);
int rightHeight = height(node->right);
return max(leftHeight, rightHeight) + 1;
}
// 示例:
cout << "Tree height: " << height(root) << endl;
```
### 4. 交换二叉树的所有左右子树
这是一个递归操作,首先检查节点是否为空,然后递归处理左右子树,并在必要时交换子节点。
```cpp
void swapChildren(TreeNode* &node) {
if (node != nullptr) {
std::swap(node->left, node->right);
swapChildren(node->left);
swapChildren(node->right);
}
}
// 示例:
swapChildren(root);
```
阅读全文