用c++建立一棵二叉树,分别对其进行先序,中序,后序,层序遍历,打印输出遍历结果,求二叉树的树的深度,统计叶子结点个数,统计总的结点个数,交换左右子树
时间: 2024-12-17 09:52:13 浏览: 16
在C++中,我们首先需要定义一个二叉树节点结构,并实现上述功能。这里是一个简单的示例:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历(根-左-右)
void preorderTraversal(TreeNode* node, string& result) {
if (node != NULL) {
result += to_string(node->val) + " ";
preorderTraversal(node->left, result);
preorderTraversal(node->right, result);
}
}
// 中序遍历(左-根-右)
void inorderTraversal(TreeNode* node, string& result) {
if (node != NULL) {
inorderTraversal(node->left, result);
result += to_string(node->val) + " ";
inorderTraversal(node->right, result);
}
}
// 后序遍历(左-右-根)
void postorderTraversal(TreeNode* node, string& result) {
if (node != NULL) {
postorderTraversal(node->left, result);
postorderTraversal(node->right, result);
result += to_string(node->val) + " ";
}
}
// 层次遍历(广度优先搜索)
void levelOrderTraversal(TreeNode* root, vector<int>& result) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
result.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
// 计算树的深度
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
// 统计叶子节点个数
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);
}
// 交换左右子树
void swapChildren(TreeNode*& node) {
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
}
```
然后你可以通过实例化`TreeNode`并调用上述函数来进行相关的操作。
阅读全文