Tìm giá trị lớn nhất (hoặc nhỏ nhất) trong cây nhị phân C++

Cho một cây nhị phân. Nhiệm vụ: Tìm giá trị lớn nhất (hoặc nhỏ nhất) trong cây nhị phân.

Mô tả: Cần tìm nút có giá trị lớn nhất và nhỏ nhất trong cây.

Ví dụ:

Đầu vào:

Đầu ra: max = 9 , min = 1

Phương pháp giải

Duyệt cây đến nút lá, tìm giá trị max của cây.

Chương trình minh họa

Ví dụ

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int findMaxNode(Node* root) {
    if (root == NULL)
        return -100;
    int maxVal = root->data;
    int leftMaxVal = findMaxNode(root->left);
    int rightMaxVal = findMaxNode(root->right);
    if (leftMaxVal > maxVal)
        maxVal = leftMaxVal;
    if (rightMaxVal > maxVal)
        maxVal = rightMaxVal;
    return maxVal;
}

int main() {
    Node* NewRoot = NULL;
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(8);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    cout << "The Maximum element of Binary Tree is " << findMaxNode(root) << endl;
    return 0;
}

Kết quả

The Maximum element of Binary Tree is 9