In tất cả cá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 cung cấp một cây tìm kiếm nhị phân và chúng ta phải in ra tất cả các nút có giá trị lẻ.

Cây tìm kiếm nhị phân là một loại cây đặc biệt có các đặc tính sau -

• Cây con bên trái luôn có các giá trị nhỏ hơn nút gốc.

• Cây con bên phải luôn có các giá trị lớn hơn nút gốc.

• Cả cây con bên trái và bên phải cũng phải tuân theo hai thuộc tính trên.

Hãy lấy một ví dụ để hiểu vấn đề -

Đầu ra - 1 3 9

Để giải quyết vấn đề này, một cách tiếp cận đơn giản sẽ là đi ngang qua cây. Trên truyền tải, chúng tôi sẽ kiểm tra giá trị của mỗi nút của cây. Nếu nút lẻ, hãy in nó ngược lại sẽ nhiều hơn vào nút tiếp theo của cây.

Độ phức tạp của chương trình sẽ phụ thuộc vào số lượng nút. Độ phức tạp về thời gian:O (n).

Ví dụ

Chương trình dưới đây cho thấy việc triển khai giải pháp của chúng tôi -

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

Đầu ra

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

1 3 9