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 tính năng Đặt hàng trước 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
6
Giải thích
Pre order traversal of tree : 1, 2, 4, 5, 3, 6, 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ự trước của cây nhị phân được thực hiện bằng cách sử dụng lệnh gọi đệ quy. Trong mỗi lần gọi, chúng ta sẽ truy cập vào nút gốc sau đó gọi preOrder () cho cây con bên trái trước và 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 findPreOrderTraversalRec(struct Node* root, int N){
static int nodeCount = 0;
if (root == NULL)
return;
if (nodeCount <= N) {
nodeCount++;
if (nodeCount == N)
cout << root->data;
findPreOrderTraversalRec(root->left, N);
findPreOrderTraversalRec(root->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 preorder traversal is ";
findPreOrderTraversalRec(root, N);
return 0;
} Đầu ra
6th node in preorder traversal is 6