พิมพ์โหนดคี่ใน Binary Search Tree ใน C++

ภาพรวมปัญหา

ได้รับ Binary Search Tree ต้องพิมพ์โหนดที่มีค่าเป็นเลขคี่ทั้งหมด

Binary Search Tree Properties

• ลูกซ้าย < โหนดแม่
• ลูกขวา > โหนดแม่
• Subtree ทั้งสองก็ต้องเป็น BST

ตัวอย่าง

Output: 1 3 9

วิธีแก้ปัญหา

Inorder Traversal (ได้ค่าจากน้อยไปมาก) ตรวจสอบแต่ละโหนด mod 2 != 0

ตัวอย่างโค้ด C++

#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 << "Nodes with odd values are:\n";
    printOddNodes(root);
    return 0;
}

ผลลัพธ์ (Output)

Nodes with odd values are:
1 3 9