คำอธิบายปัญหา
สมมติว่าเรามี preorder traversal หนึ่ง จาก traversal นี้ เราต้องสร้างต้นไม้ ดังนั้นถ้า traversal เป็น [10, 5, 1, 7, 40, 50] ต้นไม้จะเป็นดังนี้:
เพื่อแก้ปัญหานี้ เราจะใช้เทคนิคนี้: ตั้งช่วง {min... max} สำหรับแต่ละโหนด เริ่มต้นเราจะตั้งช่วงเป็น {INT_MIN... INT_MAX} โหนดแรกจะอยู่ในช่วงแน่นอน ดังนั้นหลังจากนั้นเราจะสร้างโหนดราก เพื่อสร้าง subtree ซ้าย ตั้งช่วงเป็น {INT_MIN... root->data} ถ้าค่าใดอยู่ในช่วง {INT_MIN... root->data} แสดงว่าค่านั้นเป็นส่วนของ subtree ซ้าย เพื่อสร้าง subtree ขวา ตั้งช่วงเป็น {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
