Postorder traversal ของ Binary Tree โดยไม่มี recursion และไม่มี stack ใน C++

ในปัญหานี้ เราได้รับต้นไม้ไบนารี งานของเราคือพิมพ์การข้ามผ่านของ postorder ของไบนารีทรีโดยไม่ต้องใช้ recursion และ without stack .

ต้นไม้ไบนารี เป็นต้นไม้ชนิดพิเศษที่แต่ละโหนดสามารถมีโหนดย่อยได้สูงสุด 2 โหนด

Postorder Traversal เป็นเทคนิคการสำรวจต้นไม้ โดยที่ทรีย่อยทางซ้ายแรกมีการสำรวจมากกว่าทรีย่อยทางขวา และรากจะข้ามไปในตอนท้าย

การข้ามผ่านคำสั่งหลังของต้นไม้ด้านบน − 8 4 2 7 9 6

เพื่อสำรวจต้นไม้โดยไม่ต้องใช้การเรียกซ้ำและกอง เราจะใช้เทคนิคการค้นหาเชิงลึกเป็นอันดับแรก และข้อมูลจะถูกเก็บไว้ใน ตารางแฮช .

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันนี้

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
void postOrderTraversal(struct Node* head) {
   struct Node* temp = head;
   unordered_set<Node*> visited;
   while (temp && visited.find(temp) == visited.end()) {
      if (temp->left &&
         visited.find(temp->left) == visited.end())
         temp = temp->left;
      else if (temp->right &&
         visited.find(temp->right) == visited.end())
         temp = temp->right;
      else {
         cout<<temp->data<<"\t";
         visited.insert(temp);
         temp = head;
      }
   }
}
struct Node* insertNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return (node);
}
int main(){
   struct Node* root = insertNode(6);
   root->left = insertNode(2);
   root->right = insertNode(9);
   root->left->left = insertNode(8);
   root->left->right = insertNode(4);
   root->right->left = insertNode(7);
   root->right->left->left = insertNode(13);
   cout<<"Post Order Traversal of the binary tree :\n";
   postOrderTraversal(root);
   return 0;
}

ผลลัพธ์

Post Order Traversal of the binary tree :
8    4    2    13    7    9    6

โซลูชันเดียวกันสามารถอัปเดตได้และเลิกใช้ตารางแฮชได้ เนื่องจากงานของมันคือการจัดเก็บโหนดที่เข้าชม เราจะเพิ่มแฟล็กที่เข้าชมไปยังทุกโหนดที่เป็นแผนผังเพื่อลดภาระงานในระบบ ซึ่งจะทำให้อัลกอริทึมของเราดีขึ้น

วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้แผนที่ที่ไม่เรียงลำดับ ซึ่งจะช่วยลดค่าใช้จ่ายของ trackback ไปที่ส่วนหัว

ตัวอย่าง

โปรแกรมแสดงการใช้งาน

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
   bool visited;
};
void postOrderTraversal(Node* root) {
   Node* n = root;
   unordered_map<Node*, Node*> postorder;
   postorder.insert(pair<Node*, Node*>(root, nullptr));
   while (n) {
      if (n->left && postorder.find(n->left) == postorder.end()) {
         postorder.insert(pair<Node*, Node*>(n->left, n));
         n = n->left;
      }
      else if (n->right && postorder.find(n->right) == postorder.end()) {
         postorder.insert(pair<Node*, Node*>(n->right, n));
         n = n->right;
      }
      else {
         cout<<n->data<<"\t";
         n = (postorder.find(n))->second;
      }
   }
}
struct Node* insertNode(int data) {
   struct Node* node = new Node;
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   node->visited = false;
   return (node);
}
int main() {
   struct Node* root = insertNode(6);
   root->left = insertNode(2);
   root->right = insertNode(9);
   root->left->left = insertNode(8);
   root->left->right = insertNode(4);
   root->right->left = insertNode(7);
   root->right->left->left = insertNode(13);
   cout<<"Post Order Traversal of the binary tree :\n";
   postOrderTraversal(root);
   return 0;
}

ผลลัพธ์

Post Order Traversal of the binary tree :
8    4    2    13    7    9    6