用C语言或者c++写一个完整的程序代码和运行结果,二叉树的基本操作(1)创建链式存储的二叉树,用户输入字符串,程序按照先序遍历的顺序遍历字符串并建立对应结构的二叉树(2)二叉链表的三种遍历方法:前序遍历、中序遍历、后序遍历(3)计算给定二叉树的深度、结点个数。
时间: 2024-12-02 18:15:25 浏览: 13
学习C语言的单向、双向、内核链表、链式栈、链式队列、二叉树所写的代码.zip
首先,让我们了解如何用C++编写一个简单的二叉树结构,并完成你提到的三个基本操作。
```cpp
#include <iostream>
#include <string>
// 定义二叉树节点
struct TreeNode {
char data;
TreeNode* left;
TreeNode* right;
TreeNode(char c) : data(c), left(nullptr), right(nullptr) {}
};
// 创建链式存储的二叉树函数
TreeNode* createTree(std::string input) {
int size = input.size();
if (size == 0)
return nullptr;
TreeNode* root = new TreeNode(input[0]);
std::stack<TreeNode*> s;
s.push(root);
for (int i = 1; i < size; ++i) {
char currentChar = input[i];
while (!s.empty() && s.top()->data > currentChar) { // 先序遍历左子树
TreeNode* temp = s.top();
s.pop();
s.push(temp->left);
}
if (!s.empty()) {
s.top()->right = new TreeNode(currentChar); // 添加右子节点
} else {
s.push(new TreeNode(currentChar)); // 如果栈空则添加新根节点
}
}
return root;
}
// 遍历方法
void preOrder(TreeNode* node) {
if (node != nullptr) {
std::cout << node->data << " ";
preOrder(node->left);
preOrder(node->right);
}
}
void inOrder(TreeNode* node) {
if (node != nullptr) {
inOrder(node->left);
std::cout << node->data << " ";
inOrder(node->right);
}
}
void postOrder(TreeNode* node) {
if (node != nullptr) {
postOrder(node->left);
postOrder(node->right);
std::cout << node->data << " ";
}
}
// 计算深度和节点数量
int depth(TreeNode* root) {
if (root == nullptr)
return 0;
return 1 + std::max(depth(root->left), depth(root->right));
}
int countNodes(TreeNode* root) {
if (root == nullptr)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int main() {
std::string input;
std::cout << "请输入字符串,以逗号分隔:";
std::getline(std::cin, input);
TreeNode* tree = createTree(input);
std::cout << "先序遍历结果: ";
preOrder(tree);
std::cout << "\n";
std::cout << "中序遍历结果: ";
inOrder(tree);
std::cout << "\n";
std::cout << "后序遍历结果: ";
postOrder(tree);
std::cout << "\n";
std::cout << "树的深度: " << depth(tree) << "\n";
std::cout << "树的节点数量: " << countNodes(tree) << "\n";
deleteTree(tree); // 自定义删除二叉树,防止内存泄漏
return 0;
}
```
运行此程序,用户输入一个字符串(如 "A,B,C,D,E"),然后程序会构建对应的二叉树并展示先序、中序和后序遍历的结果,以及树的深度和节点数量。
注意:这个示例代码没有包含`deleteTree`函数用于清理内存,实际项目中需要手动实现。此外,对于大型或复杂的应用场景,推荐使用库(如`std::map`等)而不是自定义二叉树结构。
阅读全文