ในปัญหานี้ เราได้รับไบนารีทรีและค่าโหนด งานของเราคือการพิมพ์ตัวต่อจากการสั่งซื้อล่วงหน้าของโหนด
ต้นไม้ไบนารี เป็นต้นไม้ชนิดพิเศษที่แต่ละโหนดรูทสามารถมีโหนดย่อยได้สูงสุด 2 โหนด
สั่งจองล่วงหน้า เป็นวิธีที่จะลัดเลาะโหนดของต้นไม้ ในนี้เราจะสำรวจโหนดรูทก่อน จากนั้นจึงออกจากชายด์และชายด์ที่ถูกต้อง
โหนดสืบทอดตำแหน่งล่วงหน้า คือโหนดที่อยู่ถัดจากโหนดในการข้ามผ่านการสั่งซื้อล่วงหน้าของโหนด
มาดูตัวอย่างทำความเข้าใจปัญหากัน
Input: 9 Output 0 Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.
ในการแก้ปัญหานี้ แนวทางของกองทัพเรือคือการค้นหาการข้ามผ่านของไบนารีทรีก่อนสั่งซื้อ จากนั้นพิมพ์องค์ประกอบที่มาหลังหมายเลขที่กำหนด
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นจะเกี่ยวข้องกับการตรวจสอบตำแหน่งของตัวเลขที่กำหนด จากนั้นจึงค้นหาตัวตายตัวแทนตามตำแหน่ง ดังนั้น หากตำแหน่งมีลูกด้านซ้าย ผู้สืบทอดตำแหน่งที่สั่งซื้อล่วงหน้าจะเป็นลูกที่ด้านซ้าย หากเป็นโหนดปลายสุดแต่เป็นโหนดลูก โหนดพี่น้องของโหนดจะเป็นตัวตายตัวแทนของการสั่งซื้อล่วงหน้า หากเป็นโหนดปลายสุดและไม่ใช่โหนดย่อย เราต้องเลื่อนขึ้นไปยังโหนดระดับบนสุดซึ่งโหนดย่อยจะเป็นผู้สืบทอดต่อจากการสั่งซื้อล่วงหน้า
โปรแกรมจะทำให้การแก้ปัญหาชัดเจนยิ่งขึ้น
ตัวอย่าง
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderSuccessorNode(Node* root, Node* n){
if (n->left)
return n->left;
Node *curr = n, *parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}
if (parent == NULL)
return NULL;
return parent->right;
}
int main(){
Node* root = insertNode(99);
root->parent = NULL;
root->left = insertNode(4);
root->left->parent = root;
root->left->left = insertNode(18);
root->left->left->parent = root->left;
root->left->right = insertNode(50);
root->left->right->parent = root->left;
root->right = insertNode(26);
root->right->parent = root;
root->right->left = insertNode(5);
root->right->left->parent = root->right;
root->right->right = insertNode(10);
root->right->right->parent = root->right;
Node* preOrder = preOrderSuccessorNode(root, root->left->right);
if (preOrder) {
cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
} else {
cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
}
return 0;
} ผลลัพธ์
Preorder successor of 50 is 26
