สมมติว่าเรามีการข้ามผ่านคำสั่งหนึ่งระดับ จากการเดินทางครั้งนี้ เราต้องสร้างต้นไม้ขึ้นมา ดังนั้นถ้าการข้ามผ่านเหมือน [7, 4, 12, 3, 6, 8, 1, 5, 10] ต้นไม้ก็จะเป็นแบบนี้ -
เพื่อแก้ปัญหานี้ เราจะใช้วิธีเรียกซ้ำ องค์ประกอบแรกจะเป็นราก องค์ประกอบที่สองจะเป็นองค์ประกอบย่อยด้านซ้าย และองค์ประกอบที่สามจะเป็นองค์ประกอบย่อยที่ถูกต้อง (หากเงื่อนไขของ BST เป็นไปตามข้อกำหนด) คุณสมบัตินี้จะเป็นที่พอใจสำหรับองค์ประกอบทั้งหมด ดังนั้นเราจะทำตามขั้นตอนเหล่านี้ -
-
ขั้นแรกเราต้องนำองค์ประกอบแรกของอาร์เรย์มาสร้างเป็นรูท
-
จากนั้นนำองค์ประกอบที่สอง หากมีขนาดเล็กกว่ารูท ให้ปล่อยให้ลูกเป็นลูกที่ไม่ใช่ลูก
-
จากนั้นโทรซ้ำขั้นตอนที่ 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
