In Tất Cả Nút Lá Của Cây Nhị Phân Từ Phải Sang Trái Trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân và phải in tất cả nút lá của cây từ phải sang trái.

Ví dụ để hiểu vấn đề:

Đầu vào:

Đầu ra – 7 4 1

Để giải quyết, ta duyệt cây nhị phân. Có hai cách:

Duyệt trước (Preorder) – Sử dụng đệ quy. Duyệt gốc, sau đó trái, rồi phải. Nếu gặp nút lá thì in, ngược lại kiểm tra con và khám phá để tìm nút lá.

Ví Dụ 1: Duyệt Trước (Preorder)

#include <iostream>
using namespace std;

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

Node* insertNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void findLeafNode(Node* root) {
    if (!root) return;
    if (!root->left && !root->right) {
        cout << root->data << "\t";
        return;
    }
    if (root->right)
        findLeafNode(root->right);
    if (root->left)
        findLeafNode(root->left);
}

int main() {
    Node* root = insertNode(21);
    root->left = insertNode(5);
    root->right = insertNode(11);
    root->left->left = insertNode(8);
    root->left->right = insertNode(98);
    root->right->left = insertNode(2);
    root->right->right = insertNode(8);
    cout << "Các nút lá của cây từ phải sang trái là:\n";
    findLeafNode(root);
    return 0;
}

Đầu Ra

Các nút lá của cây từ phải sang trái là: 18 2 98 8

Duyệt sau (Postorder) – Cách lặp – Sử dụng stack lưu dữ liệu và duyệt cây theo postorder (phải, trái, gốc) và in nút lá.

Ví Dụ 2: Duyệt Sau (Postorder) Lặp

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

struct Node {
    Node* left;
    Node* right;
    int data;
};

Node* insertNode(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}

void findLeafNode(Node* tree) {
    stack<Node*> treeStack;
    while (1) {
        if (tree) {
            treeStack.push(tree);
            tree = tree->right;
        } else {
            if (treeStack.empty())
                break;
            else {
                if (treeStack.top()->left == NULL) {
                    tree = treeStack.top();
                    treeStack.pop();
                    if (tree->right == NULL)
                        cout << tree->data << "\t";
                }
                while (tree == treeStack.top()->left) {
                    tree = treeStack.top();
                    treeStack.pop();
                    if (treeStack.empty())
                        break;
                }
                if (!treeStack.empty())
                    tree = treeStack.top()->left;
                else
                    tree = NULL;
            }
        }
    }
}

int main() {
    Node* root = insertNode(21);
    root->left = insertNode(5);
    root->right = insertNode(11);
    root->left->left = insertNode(8);
    root->left->right = insertNode(98);
    root->right->left = insertNode(2);
    root->right->right = insertNode(18);
    cout << "Các nút lá của cây từ phải sang trái là:\n";
    findLeafNode(root);
    return 0;
}

Đầu Ra

Các nút lá của cây từ phải sang trái là: 18 2 98 8