Trong bài toán này, chúng ta được cung cấp một cây nhị phân và một số nguyên N. Nhiệm vụ là tìm ra nút thứ n trong trình duyệt nhỏ hơn của Cây nhị phân.
Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con.
Traversal là một quá trình để truy cập tất cả các nút của một cây và có thể in ra cả giá trị của chúng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 6
Đầu ra
3
Giải thích
inorder traversal of tree : 4, 2, 5, 1, 6, 3, 7
Phương pháp tiếp cận giải pháp
Ý tưởng là sử dụng trình duyệt theo thứ tự của cây nhị phân được thực hiện bằng cách sử dụng các lệnh gọi đệ quy. Trong mỗi lần gọi, chúng ta sẽ gọi preOrder () cho cây con bên trái trước tiên và duyệt qua nút gốc sau đó gọi preOrder (). Trong quá trình truyền tải này, chúng tôi sẽ đếm số lượng nút và in ra nút có số lượng là N.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* createNode(int item){
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void findInOrderTraversalRec(struct Node* node, int N){
static int count = 0;
if (node == NULL)
return;
if (count <= N) {
findInOrderTraversalRec(node->left, N);
count++;
if (count == N)
cout<<node->data;
findInOrderTraversalRec(node->right, N);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
int N = 6;
cout<<N<<"th node in inorder traversal is ";
findInOrderTraversalRec(root, N);
return 0;
} Đầu ra
6th node in inorder traversal is 3