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