คำอธิบายปัญหา
สมมติว่าเรามี preorder traversal หนึ่ง จาก traversal นี้ เราต้องสร้างต้นไม้ ดังนั้นถ้า traversal เป็น [10, 5, 1, 7, 40, 50] ต้นไม้จะเป็นดังนี้:
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
สร้าง stack ว่าง
ทำนำค่าแรกเป็นราก (root) และ push เข้า stack
ตอนนี้ ทำการ pop ซ้ำๆ ในขณะที่ stack ไม่ว่าง และค่าถัดไปมากกว่าองค์ประกอบบนสุดของ stack ทำให้ค่านี้เป็นลูกขวาของโหนดที่ pop ล่าสุด ตอนนี้ push โหนดใหม่เข้า stack
เมื่อค่าถัดไปน้อยกว่าองค์ประกอบบนสุด ทำให้มันเป็นลูกซ้ายของ stack top ตอนนี้ push โหนดใหม่เข้า stack
ทำซ้ำขั้นตอน 2 และ 3 จนกว่าจะตรวจสอบทุกองค์ประกอบใน preorder list
ตัวอย่างโค้ด
#include <iostream> #include <stack> 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* constructTree ( int pre[], int size ) { stack<node*> stk; node* root = getNode( pre[0] ); stk.push(root); int i; node* temp; for ( i = 1; i < size; ++i ) { temp = NULL; while ( !stk.empty() && pre[i] > stk.top()->data ) { temp = stk.top(); stk.pop(); } if ( temp != NULL) { temp->right = getNode( pre[i] ); stk.push(temp->right); } else { node* peek_node = stk.top(); peek_node->left = getNode( pre[i] ); stk.push(stk.top()->left); } } return root; } 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 = constructTree(pre, size); cout << "Inorder traversal: "; inord(root); }ผลลัพธ์
Inorder traversal: 1 5 7 10 40 50
