[SAP/C++] BST from postorder

난이도 : 중

 

후순위 운행으로 이진탐색 트리 만들기 

 

BST : Binary Search Tree (이진 탐색 트리)

이진 탐색 트리 : 탐색하고자 하는 key값을 배열의 중앙값과 비교하여, 

크면 오른쪽 list에 존재하고, 작으면 왼쪽 list에 존재한다. 

 

PostOrder : 후순위 운행 L->R->V 순으로 탐색을 진행

 

후순위 운행으로 주어진 그래프를 탐색하여, 이를 BST로 만들기

이때 그래프는 배열로 주어져있음

 

 

// postorder : 후순위 운행 L-R-V
Node* BST(Node* root,int key)
{
    if(root==NULL)
        root=new Node(key);
    else if(root->data > key)
        root->left=BST(root->left,key); //root->left를 root로 재귀적으로 진행 
    else
        root->right=BST(root->right,key);//root->right를 root로 재귀적으로 진행 
        
    return root;
}

Node *constructTree (int post[], int size)
{
    if(size==0)
        return NULL;
        
    Node* root=NULL;
    
    //postorder이므로 L->R->V라 거꾸로진행했을 때 가장 마지막이 root
    for(int i=size-1;i>=0;i--)
        root=BST(root,post[i]);
        
    return root;
}