ในปัญหานี้ เราได้รับไบนารีทรีและค่าโหนด งานของเราคือพิมพ์พรีออเดอร์พรีออร์เดอร์ของโหนด
ต้นไม้ไบนารี เป็นต้นไม้ชนิดพิเศษที่แต่ละโหนดรูทสามารถมีโหนดย่อยได้สูงสุด 2 โหนด
สั่งจองล่วงหน้า เป็นวิธีที่จะลัดเลาะโหนดของต้นไม้ ในนี้เราจะสำรวจโหนดรูทก่อน จากนั้นจึงออกจากชายด์และชายด์ที่ถูกต้อง
สั่งซื้อโหนดรุ่นก่อนล่วงหน้า คือโหนดที่มาก่อนโหนดในการสั่งซื้อล่วงหน้าของโหนด
มาดูตัวอย่างทำความเข้าใจปัญหากัน
Input: 1 Output: 9
เพื่อแก้ปัญหานี้ กองทัพเรือ วิธีการคือการค้นหาการข้ามผ่านของการสั่งซื้อล่วงหน้าของไบนารีทรีแล้วพิมพ์องค์ประกอบที่มาหลังหมายเลขที่กำหนด
วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นจะเกี่ยวข้องกับการตรวจสอบตำแหน่งของตัวเลขที่กำหนด จากนั้นจึงค้นหาหมายเลขก่อนหน้าตามตำแหน่ง หากโหนดเป็นโหนดรูท ให้คืนค่า NULL ไม่ใช่รุ่นก่อน หากโหนดเป็นชายด์ที่ถูกต้อง ลูกด้านซ้ายจะเป็นรุ่นก่อน
โปรแกรมแสดงการดำเนินการแก้ไข
ตัวอย่าง
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
struct Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderPredecessorNode(Node* root, Node* n){
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->left == NULL || parent->left == n)
return parent;
Node* curr = parent->left;
while (curr->right != NULL)
curr = curr->right;
return curr;
}
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* preOrderPredecessor = preOrderPredecessorNode(root, root->left->right);
if (preOrderPredecessor)
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is "<<preOrderPredecessor->key;
else
cout<<"Preorder Predecessor of "<<root->left->right->key<<" is NULL";
return 0;
} ผลลัพธ์
Preorder Predecessor of 50 is 18
