c++用链表实现根据输入的数据建立一个二叉树,输出树型结构二叉树,输出其前序 中序 和后序遍历的结果,输出树的深度,最大元,最小元的完整无错误代码
时间: 2024-09-21 19:05:33 浏览: 41
在C++中,我们可以使用链表构建二叉搜索树(BST),然后通过递归的方式实现前序、中序和后序遍历,并计算树的深度、最大值和最小值。下面是一个完整的示例:
首先,我们需要创建二叉树节点的结构体:
```cpp
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
接下来,我们实现插入函数,以及根据输入数据构造二叉树:
```cpp
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) return new TreeNode(val);
if (val < root->val) {
root->left = insertIntoBST(root->left, val);
} else {
root->right = insertIntoBST(root->right, val);
}
return root;
}
void buildBST(std::vector<int>& nums, TreeNode*& root) {
for (int num : nums) {
root = insertIntoBST(root, num);
}
}
```
接着,我们定义前序、中序和后序遍历的辅助函数:
```cpp
void preOrderTraversal(TreeNode* node, std::string& result) {
if (node == nullptr) return;
result += to_string(node->val) + " ";
preOrderTraversal(node->left, result);
preOrderTraversal(node->right, result);
}
std::string inOrderTraversal(TreeNode* node) {
std::string result;
if (node == nullptr) return result;
result = inOrderTraversal(node->left) + to_string(node->val) + " ";
result += inOrderTraversal(node->right);
return result;
}
std::string postOrderTraversal(TreeNode* node) {
std::string result;
if (node == nullptr) return result;
result = postOrderTraversal(node->left) + postOrderTraversal(node->right) + to_string(node->val) + " ";
return result;
}
```
最后,我们提供函数获取树的深度、最大值和最小值:
```cpp
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
int findMinAndMax(TreeNode* root) {
if (root == nullptr) return -1; // 如果为空,返回-1表示未找到
int min_val = findMinAndMax(root->left);
int max_val = findMinAndMax(root->right);
return root->val > min_val && root->val < max_val ? root->val : std::min(min_val, max_val);
}
```
你可以使用以下方式调用这些功能:
```cpp
int main() {
std::vector<int> nums = {5, 3, 7, 2, 4, 6, 8};
TreeNode* root = nullptr;
buildBST(nums, root);
std::cout << "Preorder traversal: " << preOrderTraversal(root, "") << std::endl;
std::cout << "Inorder traversal: " << inOrderTraversal(root) << std::endl;
std::cout << "Postorder traversal: " << postOrderTraversal(root) << std::endl;
int depth = maxDepth(root);
int min_max = findMinAndMax(root);
std::cout << "Tree depth: " << depth << ", Minimum value: " << min_max << ", Maximum value: " << min_max << std::endl;
return 0;
}
```