In Tất Cả Nút Chẵn Của Cây Tìm Kiếm Nhị Phân Trong C++

Trong bài toán này, chúng ta được cho một cây tìm kiếm nhị phân. Nhiệm vụ là in tất cả các nút có giá trị chẵn của cây.

Cây tìm kiếm nhị phân (BST) là cây nhị phân thỏa mãn:

• Cây con trái luôn chứa nút có giá trị nhỏ hơn nút cha.
• Cây con phải luôn chứa nút có giá trị lớn hơn nút cha.
• Tất cả nút phải tuân theo 2 quy tắc trên.

Ví dụ cây BST:

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

Đầu ra – 2 4 6 8

Để giải quyết, ta duyệt tất cả nút của BST và kiểm tra giá trị nút hiện tại. Nếu chẵn thì in, ngược lại bỏ qua.

Ví Dụ

Mã minh họa giải pháp:

#include <iostream>
using namespace std;

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

Node* newNode(int item) {
    Node* temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

Node* insertNode(Node* node, int key) {
    if (node == NULL)
        return newNode(key);
    if (key < node->key)
        node->left = insertNode(node->left, key);
    else
        node->right = insertNode(node->right, key);
    return node;
}

void printEvenNode(Node* root) {
    if (root != NULL) {
        printEvenNode(root->left);
        if (root->key % 2 == 0)
            cout << root->key << "\t";
        printEvenNode(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insertNode(root, 54);
    root = insertNode(root, 43);
    root = insertNode(root, 12);
    root = insertNode(root, 30);
    root = insertNode(root, 89);
    root = insertNode(root, 67);
    root = insertNode(root, 80);
    cout << "Tất cả nút chẵn của cây là:\n";
    printEvenNode(root);
    return 0;
}

Đầu Ra

Tất cả nút chẵn của cây là:

12 30 54 80