Trong bài toán này, chúng ta được cung cấp một BT cây nhị phân và một giá trị khóa. Nhiệm vụ của chúng ta là Tìm nút bên phải tiếp theo của một khóa nhất định.
Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
key = 4
Đầu ra
5
Giải thích
Phần tử bên cạnh nút 4 là 5.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề này là duyệt qua cây nhị phân bằng cách sử dụng duyệt thứ tự mức. Và đối với giá trị khóa đã cho, chúng tôi sẽ kiểm tra xem có tồn tại một nút bên cạnh nút ở cùng mức trong truyền tải hay không. Nếu Có, hãy trả về nút tiếp theo, nếu không thì trả về NULL.
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>
#include <queue>
using namespace std;
struct node {
struct node *left, *right;
int key;
};
node* newNode(int key) {
node *temp = new node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
node* findNextRightNodeBT(node *root, int k) {
if (root == NULL)
return 0;
queue<node *> nodeVal;
queue<int> nodeLevel;
int level = 0;
nodeVal.push(root);
nodeLevel.push(level);
while (nodeVal.size()) {
node *node = nodeVal.front();
level = nodeLevel.front();
nodeVal.pop();
nodeLevel.pop();
if (node->key == k) {
if (nodeLevel.size() == 0 || nodeLevel.front() != level)
return NULL;
return nodeVal.front();
}
if (node->left != NULL) {
nodeVal.push(node->left);
nodeLevel.push(level+1);
}
if (node->right != NULL) {
nodeVal.push(node->right);
nodeLevel.push(level+1);
}
}
return NULL;
}
int main() {
node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
int key = 4;
cout<<"The next right node of the node "<<key<<" is ";
node *nextNode = findNextRightNodeBT(root, key);
if(nextNode != NULL)
cout<<nextNode->key;
else
cout<<"not available";
return 0;
} Đầu ra
The next right node of the node 4 is 5