In Tất Cả Nút Lẻ 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 và phải in tất cả nút có giá trị lẻ.

Cây tìm kiếm nhị phân (BST) là cây đặc biệt có các tính chất:

• Cây con trái luôn có giá trị nhỏ hơn nút gốc.
• Cây con phải luôn có giá trị lớn hơn nút gốc.
• Cả hai cây con cũng phải tuân theo hai tính chất trên.

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

Đầu ra – 1 3 9

Để giải quyết, cách đơn giản là duyệt cây. Khi duyệt, kiểm tra giá trị mỗi nút. Nếu lẻ thì in, ngược lại chuyển nút tiếp theo.

Độ phức tạp phụ thuộc vào số nút. Độ phức tạp thời gian: O(n).

Ví Dụ

Chương trình minh họa giải pháp:

#include <bits/stdc++.h>
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 printOddNodes(Node* root) {
    if (root != NULL) {
        printOddNodes(root->left);
        if (root->key % 2 != 0)
            cout << root->key << "\t";
        printOddNodes(root->right);
    }
}

int main() {
    Node* root = NULL;
    root = insertNode(root, 6);
    root = insertNode(root, 3);
    root = insertNode(root, 1);
    root = insertNode(root, 4);
    root = insertNode(root, 9);
    root = insertNode(root, 8);
    root = insertNode(root, 10);
    cout << "Các nút có giá trị lẻ là:\n";
    printOddNodes(root);
    return 0;
}

Đầu Ra

Các nút có giá trị lẻ là:

1 3 9