Trong bài toán này, chúng ta được đưa ra một cây tìm kiếm nhị phân. Nhiệm vụ của chúng tôi là in tất cả các nút có giá trị chẵn của cây tìm kiếm nhị phân.
Cây tìm kiếm nhị phân là một cây nhị phân tuân theo điều kiện sau -
-
Cây con bên trái luôn chứa các nút có giá trị nhỏ hơn nút mẹ.
-
Đúng, cây con luôn chứa các nút có giá trị lớn hơn nút mẹ.
-
Tất cả các nút phải tuân theo 2 quy tắc trên.
Ví dụ về cây tìm kiếm nhị phân -
Hãy lấy một ví dụ để hiểu vấn đề -
Đầu ra - 2 4 6 8
Để giải quyết vấn đề này, chúng ta sẽ phải duyệt qua tất cả các nút của cây tìm kiếm nhị phân và kiểm tra giá trị của nút hiện tại. Nếu nó là số chẵn thì hãy in nút, nếu không thì bỏ nó đi.
Ví dụ
Đoạn mã dưới đây sẽ minh họa hoạt động của logic của chúng tôi -
#include <iostream>
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 printEvenNode(Node* root){
if (root != NULL) {
printEvenNode(root->left);
if (root->key % 2 == 0)
cout<<root->key<<"\t";
printEvenNode(root->right);
}
}
int main(){
Node* root = NULL;
root = insertNode(root, 54);
root = insertNode(root, 43);
root = insertNode(root, 12);
root = insertNode(root, 30);
root = insertNode(root, 89);
root = insertNode(root, 67);
root = insertNode(root, 80);
cout<<"All even nodes of the tree are :\n";
printEvenNode(root);
return 0;
} Đầu ra
Tất cả các nút chẵn của cây là -
12 30 54 80