하나의 사전 주문 순회가 있다고 가정합니다. 이 순회에서. 트리를 생성해야 합니다. 따라서 순회가 [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