ในปัญหานี้ เราจะได้รับไบนารีทรีและโหนด หน้าที่ของเราคือพิมพ์ลำดับหลังของโหนดในทรีไบนารี
ไบนารี ต้นไม้ เป็นต้นไม้ชนิดพิเศษที่แต่ละโหนดสามารถมีโหนดย่อยได้สูงสุด 2 โหนด
การข้ามผ่านของการสั่งซื้อทางไปรษณีย์ เป็นเทคนิคการสำรวจต้นไม้ โดยที่ทรีย่อยทางซ้ายแรกมีการสำรวจมากกว่าทรีย่อยทางขวา และรากจะข้ามไปในตอนท้าย
การข้ามผ่านคำสั่งของต้นไม้ด้านบน:8 4 2 7 9 6
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − binary tree ในตัวอย่างด้านบน node=7
ผลผลิต − 9
คำอธิบาย − เราเห็นมันในการข้ามผ่านหลังลำดับของไบนารีทรี
ในการแก้ปัญหานี้ วิธีแก้ปัญหาที่ง่าย ง่าย และไม่ใช่วิธีง่ายๆ ก็คือการค้นหาการข้ามผ่านรายการสั่งซื้อแล้วพิมพ์หมายเลขข้างๆ ในการข้ามผ่าน
แต่เราต้องเรียนรู้วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้น
วิธีแก้ปัญหาที่มีประสิทธิภาพจะเกี่ยวข้องกับการใช้การสังเกตทั่วไปเกี่ยวกับการข้ามผ่านของคำสั่งซื้อขาย
-
เนื่องจาก root เป็นโหนดสุดท้ายในการข้ามผ่าน postorder ตัวตายตัวแทนจึงเป็น NULL
-
ในกรณีที่โหนดปัจจุบันเป็นโหนดย่อยที่ถูกต้อง โหนดหลักจะเป็นผู้สืบทอด
-
ในกรณีที่โหนดปัจจุบันถูกปล่อยให้เป็นลูก จากนั้น
-
หากไม่มีพี่น้องที่ถูกต้อง ผู้สืบทอดคือโหนดหลัก
-
หากพี่น้องที่ถูกต้องมีอยู่ แสดงว่าโหนดหรือลูกที่อยู่ทางซ้ายสุดจะเป็นตัวตายตัวแทน
-
วิธีนี้ได้ผล เวลาซับซ้อนคือ O(h) ความสูงของต้นไม้
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int value;
};
struct Node* insertNode(int value) {
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->value = value;
return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->right == NULL || parent->right == n)
return parent;
Node* curr = parent->right;
while (curr->left != NULL)
curr = curr->left;
return curr;
}
int main(){
struct Node* root = insertNode(6);
root->parent = NULL;
root->left = insertNode(2);
root->left->parent = root;
root->left->left = insertNode(8);
root->left->left->parent = root->left;
root->left->right = insertNode(4);
root->left->right->parent = root->left;
root->right = insertNode(9);
root->right->parent = root;
root->right->left = insertNode(7);
root->right->left->parent = root->right;
root->left->right->left = insertNode(14);
struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
if (successorNode)
cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
} ผลลัพธ์
Postorder successor of 4 is 2
