Tìm nút lá trái sâu nhất trong cây nhị phân C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ tìm nút lá (leaf node) trái sâu nhất trong một cây nhị phân (binary tree).

Ý tưởng thuật toán

Sử dụng đệ quy với tham số isLeftNode để theo dõi xem nút hiện tại có phải là con trái của cha hay không. Khi gặp nút lá bên trái, cập nhật kết quả. Do duyệt trái trước phải, nút lá trái sâu nhất sẽ được tìm thấy cuối cùng.

Các bước thực hiện

1. Định nghĩa cấu trúc Node với ký tự dữ liệu, con trỏ left và right.
2. Viết hàm tạo nút mới.
3. Xây dựng cây nhị phân mẫu.
4. Viết hàm đệ quy getDeepestLeftLeafNode nhận tham số: nút gốc, isLeftNode, con trỏ kết quả.
5. Nếu nút là lá và isLeftNode == true, cập nhật kết quả.
6. Đệ quy sang trái (isLeftNode = true) rồi sang phải (isLeftNode = false).

Mã nguồn ví dụ

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char data;
    struct Node *left, *right;
};

Node* addNewNode(char data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void getDeepestLeftLeafNode(Node* root, bool isLeftNode, Node** resultPointer) {
    if (root == NULL) return;
    if (isLeftNode && !root->left && !root->right) {
        *resultPointer = root;
        return;
    }
    getDeepestLeftLeafNode(root->left, true, resultPointer);
    getDeepestLeftLeafNode(root->right, false, resultPointer);
}

int main() {
    Node* root = addNewNode('A');
    root->left = addNewNode('B');
    root->right = addNewNode('C');
    root->left->left = addNewNode('D');
    root->right->left = addNewNode('E');
    root->right->right = addNewNode('F');
    root->right->left->right = addNewNode('G');
    Node* result = NULL;
    getDeepestLeftLeafNode(root, false, &result);
    if (result) {
        cout << "Nút lá trái sâu nhất là: " << result->data << endl;
    } else {
        cout << "Không có nút lá trái trong cây" << endl;
    }
    return 0;
}

Kết quả đầu ra

Nút lá trái sâu nhất là: D

Kết luận

Nút D là nút lá trái sâu nhất trong cây mẫu. Thuật toán hoạt động đúng nhờ duyệt trái trước phải. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.