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