พิมพ์โหนดคี่ทั้งหมดของ Binary Search Tree ใน C++

ในปัญหานี้ เราได้รับแผนผังการค้นหาแบบไบนารี และเราต้องพิมพ์โหนดทั้งหมดที่มีค่าคี่

แผนผังการค้นหาแบบไบนารี เป็นต้นไม้ชนิดพิเศษที่มีคุณสมบัติดังต่อไปนี้ −

• ทรีย่อยด้านซ้ายมีค่าน้อยกว่าโหนดรูทเสมอ

• ทรีย่อยที่ถูกต้องมีค่ามากกว่าโหนดรูทเสมอ

• ทั้งแผนผังย่อยด้านซ้ายและขวาควรเป็นไปตามคุณสมบัติทั้งสองข้างต้นด้วย

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −

ผลผลิต − 1 3 9

ในการแก้ปัญหานี้ วิธีง่ายๆ คือการสำรวจต้นไม้ ในการข้ามผ่าน เราจะตรวจสอบค่าของแต่ละโหนดของต้นไม้ หากโหนดเป็นเลขคี่ ให้พิมพ์ไปที่โหนดถัดไปของทรี

ความซับซ้อนของโปรแกรมจะขึ้นอยู่กับจำนวนโหนด ความซับซ้อนของเวลา:O(n)

ตัวอย่าง

โปรแกรมด้านล่างแสดงการใช้งานโซลูชันของเรา -

#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;
}

ผลลัพธ์

โหนดที่มีค่าคี่คือ -

1 3 9