ในปัญหานี้ เราได้รับไบนารีทรี BT และค่าคีย์ งานของเราคือค้นหาโหนดถัดไปด้านขวาของคีย์ที่กำหนด
Binary Tree เป็นโครงสร้างข้อมูลพิเศษที่ใช้เพื่อการจัดเก็บข้อมูล
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
key = 4
ผลลัพธ์
5
คำอธิบาย
องค์ประกอบถัดจากโหนด 4 คือ 5
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือโดยการสำรวจต้นไม้ไบนารีโดยใช้การข้ามผ่านคำสั่งระดับ และสำหรับค่าคีย์ที่กำหนด เราจะตรวจสอบว่ามีโหนดอยู่ถัดจากโหนดที่ระดับเดียวกันในการข้ามผ่านหรือไม่ ถ้าใช่ ให้คืนค่าโหนดถัดไป ไม่เช่นนั้นให้คืนค่า NULL
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The next right node of the node 4 is 5
