สมมติว่าเรามีการสั่งซื้อล่วงหน้าหนึ่งครั้ง จากการเดินทางครั้งนี้ เราต้องสร้างต้นไม้ ดังนั้นถ้าการข้ามผ่านเป็น [10, 5, 1, 7, 40, 50] ต้นไม้ก็จะเป็นแบบนั้น -
เพื่อแก้ปัญหานี้ เราจะใช้เคล็ดลับนี้ เคล็ดลับคือการตั้งค่าช่วง {นาที... สูงสุด} สำหรับแต่ละโหนด ตอนแรก เราจะเริ่มต้นช่วงเป็น {INT_MIN… INT_MAX} โหนดแรกจะอยู่ในช่วงที่แน่นอน ดังนั้นหลังจากนั้นเราจะสร้างโหนดรูท ในการสร้างทรีย่อยด้านซ้าย ให้ตั้งค่าช่วงเป็น {INT_MIN… root->data} หากค่าอยู่ในช่วง {INT_MIN… root->data} แสดงว่าค่านั้นเป็นส่วนหนึ่งของทรีย่อยด้านซ้าย ในการสร้างแผนผังย่อยที่ถูกต้อง ให้ตั้งค่าช่วงเป็น {root->data… max… INT_MAX}
ตัวอย่าง
#include <iostream>
using namespace std;
class node {
public:
int data;
node *left;
node *right;
};
node* getNode (int data) {
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
node* makeTreeUtil( int pre[], int* preord_index, int key, int min, int max, int size ) {
if( *preord_index >= size )
return NULL;
node* root = NULL;
if( key > min && key < max ){
root = getNode( key );
*preord_index += 1;
if (*preord_index < size){
root->left = makeTreeUtil( pre, preord_index, pre[*preord_index], min, key, size );
root->right = makeTreeUtil( pre, preord_index, pre[*preord_index],key, max, size );
}
}
return root;
}
node *makeTree (int pre[], int size) {
int preord_index = 0;
return makeTreeUtil( pre, &preord_index, pre[0], INT_MIN, INT_MAX, size );
}
void inord (node* node) {
if (node == NULL)
return;
inord(node->left);
cout << node->data << " ";
inord(node->right);
}
int main () {
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
node *root = makeTree(pre, size);
cout << "Inorder traversal: ";
inord(root);
} ผลลัพธ์
Inorder traversal: 1 5 7 10 40 50
