C++で二分探索木のすべての奇数ノードを印刷します

この問題では、二分探索木が与えられ、奇数の値を持つすべてのノードを出力する必要があります。

二分探索木 は、次のプロパティを持つ特殊なタイプのツリーです-

• 左側のサブツリーには、常にルートノードよりも小さい値があります。

• 右側のサブツリーには、常にルートノードよりも大きい値があります。

• 左右のサブツリーも、上記の2つのプロパティに従う必要があります。

問題を理解するために例を見てみましょう-

出力 − 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