使用c++语言,用括号表示法构造二叉树1(2(4)(5))(3),实现(1)创建二叉树(由括号表示法字符串str创建二叉树) (2)销毁二叉树 (3)查找结点 (4)找孩子节点 (5)求高度 输出二叉树的功能,不要省略函数
时间: 2024-12-28 09:36:48 浏览: 1
在C++中,我们可以使用递归的方式来构建和操作二叉树。首先,我们需要定义一个二叉树节点的结构体或类。这里假设我们有一个`TreeNode`类,包含一个整数值`val`和两个指向子节点的指针`left`和`right`。
```cpp
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
// 构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 创建二叉树的函数
TreeNode* createTreeFromBracket(const string& str) {
if (str.empty()) return nullptr;
int start = 0;
TreeNode* root = new TreeNode(stoi(str.substr(1, str[0] - '1')));
for (int i = 1; i < str.length(); ++i) {
if (str[i] == '(') start++;
else if (str[i] == ')') start--;
else if (start == 0) {
if (str[i] == 'L') {
root->left = createTreeFromBracket(string(str.begin() + i + 1, str.end()));
} else {
root->right = createTreeFromBracket(string(str.begin() + i + 1, str.end()));
}
break;
}
}
return root;
}
// 销毁二叉树
void destroyTree(TreeNode*& node) {
if (node != nullptr) {
destroyTree(node->left);
destroyTree(node->right);
delete node;
node = nullptr;
}
}
// 查找结点
bool searchNode(TreeNode* root, int target) {
if (root == nullptr || root->val == target) return root != nullptr;
return searchNode(root->left, target) || searchNode(root->right, target);
}
// 找孩子节点
TreeNode* findChildNode(TreeNode* parent, int childIndex, bool isLeft) {
if (isLeft && parent->left != nullptr) return parent->left;
if (!isLeft && parent->right != nullptr) return parent->right;
return nullptr;
}
// 求高度
int height(TreeNode* root) {
if (root == nullptr) return 0;
return max(height(root->left), height(root->right)) + 1;
}
// 输出二叉树功能
void printTree(TreeNode* root, int level = 0) {
if (root == nullptr) return;
cout << setw(level * 2) << root->val << endl;
printTree(root->left, level + 1);
printTree(root->right, level + 1);
}
```
上述代码实现了从括号表示法创建、销毁二叉树,以及查找、访问孩子节点和计算高度的基本功能。`printTree`函数用于层级遍历打印树节点值,可以作为输出二叉树内容的方式。每个功能都有相应的辅助函数支持。
阅读全文