c++初始化一个数据元素为字符串类型的二叉树,并对其实现创建及求最大深度操作。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
时间: 2024-04-29 11:21:25 浏览: 61
可以使用如下的代码实现:
```cpp
#include <iostream>
#include <string>
using namespace std;
struct Node {
string data;
Node* left;
Node* right;
Node(string val) : data(val), left(nullptr), right(nullptr) {}
};
class BinaryTree {
public:
BinaryTree() : root(nullptr) {}
~BinaryTree() { destroy(root); }
void createTree() { createTreeHelper(root); }
int maxDepth() { return maxDepthHelper(root); }
private:
Node* root;
void destroy(Node* node) {
if (node != nullptr) {
destroy(node->left);
destroy(node->right);
delete node;
}
}
void createTreeHelper(Node*& node) {
string val;
cin >> val;
if (val == "null") {
node = nullptr;
}
else {
node = new Node(val);
createTreeHelper(node->left);
createTreeHelper(node->right);
}
}
int maxDepthHelper(Node* node) {
if (node == nullptr) {
return 0;
}
else {
int leftDepth = maxDepthHelper(node->left);
int rightDepth = maxDepthHelper(node->right);
return max(leftDepth, rightDepth) + 1;
}
}
};
int main() {
BinaryTree tree;
cout << "请输入二叉树节点值,使用 null 表示空节点:" << endl;
tree.createTree();
cout << "二叉树的最大深度为:" << tree.maxDepth() << endl;
return 0;
}
```
这个程序中,我们定义了一个 `Node` 结构体,表示二叉树的一个节点,包含一个字符串类型的数据,以及左右子节点的指针。然后,我们定义了一个 `BinaryTree` 类,其中包含了二叉树的根节点指针 `root`,以及创建二叉树和求最大深度的成员函数 `createTree` 和 `maxDepth`。
在 `createTree` 函数中,我们首先输入一个字符串,如果该字符串为 "null",则表示当前节点为空,否则我们创建一个新的节点,并递归地创建其左右子树。
在 `maxDepth` 函数中,我们首先判断当前节点是否为空,如果为空则返回 0,否则我们递归地计算左右子树的最大深度,并返回较大值加上 1。
最后,在 `main` 函数中,我们首先创建一个 `BinaryTree` 对象,然后调用 `createTree` 函数创建二叉树,再调用 `maxDepth` 函数求最大深度并输出结果。
阅读全文