คำอธิบายปัญหา
สมมติว่าเรามี level order traversal หนึ่ง จาก traversal นี้ เราต้องสร้างต้นไม้ (tree) ดังนั้นถ้า traversal เป็น [7, 4, 12, 3, 6, 8, 1, 5, 10] ต้นไม้จะเป็นดังนี้:
เพื่อแก้ปัญหานี้ เราจะใช้วิธีเวียนเกิด (recursive) องค์ประกอบแรกจะเป็นราก (root) องค์ประกอบที่สองจะเป็นลูกซ้าย และองค์ประกอบที่สามจะเป็นลูกขวา (ถ้าเงื่อนไข BST ตรง) คุณสมบัตินี้จะเป็นจริงสำหรับทุกองค์ประกอบ ดังนั้นเราจะทำตามขั้นตอนเหล่านี้:
ก่อนอื่น เราต้องนำองค์ประกอบแรกของอาร์เรย์ มาทำเป็นราก (root)
จากนั้นนำองค์ประกอบที่สอง ถ้าน้อยกว่าราก ทำเป็นลูกซ้าย มิฉะนั้นลูกขวา
จากนั้นเรียกขั้นตอนที่ 2 แบบเวียนเกิด เพื่อสร้าง BST
ตัวอย่างโค้ด
#include <iostream> using namespace std; class Node { public: int data; Node *left, *right; }; Node* getNode(int data) { Node *newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } Node *lvlOrd(Node *root , int data) { if(root==NULL){ root = getNode(data); return root; } if(data <= root->data) root->left = lvlOrd(root->left, data); else root->right = lvlOrd(root->right, data); return root; } Node* makeTree(int arr[], int n) { if(n==0) return NULL; Node *root= NULL; for(int i=0;i<n;i++) root = lvlOrd(root , arr[i]); return root; } void inord(Node* root) { if (!root) return; inord(root->left); cout << root->data << " "; inord(root->right); } int main() { int arr[] = {7, 4, 12, 3, 6, 8, 1, 5, 10}; int n = sizeof(arr) / sizeof(arr[0]); Node *root = makeTree(arr, n); cout << "Inorder Traversal: "; inord(root); }ผลลัพธ์
Inorder Traversal: 1 3 4 5 6 7 8 10 12
