假设二叉树采用二叉链存储结构,设计一个C++算法求非空二叉树中的最大结点值
时间: 2024-03-01 18:04:14 浏览: 69
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
好的,我可以为您编写该算法。以下是C++代码实现:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int findMax(TreeNode* root) {
if(root == NULL) // 如果树为空,则返回-1
return -1;
int maxVal = root->val; // 初始化最大值为根节点的值
int leftMax = findMax(root->left); // 递归查找左子树中的最大值
int rightMax = findMax(root->right); // 递归查找右子树中的最大值
if(leftMax > maxVal) // 如果左子树中的最大值大于当前最大值,则更新最大值
maxVal = leftMax;
if(rightMax > maxVal) // 如果右子树中的最大值大于当前最大值,则更新最大值
maxVal = rightMax;
return maxVal;
}
int main() {
// 创建一棵二叉树
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(8);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(4);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(10);
// 查找最大结点值
int maxVal = findMax(root);
cout << "The maximum value in the binary tree is: " << maxVal << endl;
return 0;
}
```
该算法的时间复杂度为O(n),其中n为二叉树中的结点数。
阅读全文