PTA 7-23 포크 트리 복원

1670 단어
지식:
  • 앞의 순서와 중간의 순서에 따라 두 갈래 나무를 복원한다

  • 두 갈래 나무의 선차적 역행 서열과 중차적 역행 서열을 정하고 이 두 갈래 나무의 높이를 계산해야 한다.
    두 갈래 나무의 성질에 따라 만약에 우리가 두 갈래 나무의 일종의 역행 방식의 결과만 제시한다면 두 갈래 나무를 완전히 확정할 수 없다. 이때의 두 갈래 나무는 여러 가지 형태를 가지고 있을 수 있다.그러나 우리가 두 갈래 나무의 두 가지 다른 역행 방식을 제시할 때 두 갈래 나무를 완전히 확정할 수 있다.
    이곳은 이전에 차례와 중차례를 예로 들 수 있다.만일 우리가 두 그루의 두 갈래 나무의 앞가운데 차례를 각각
    앞 순서: ABDFGHIEC 내 순서: FDHGIBEAC
  • 앞에서 두루 훑어보는 성질로 우리는 A가 틀림없이 이 나무의 뿌리 결점이라는 것을 알 수 있다
  • 중서를 두루 훑어보면 알 수 있듯이 A의 왼쪽은 틀림없이 A의 왼쪽나무이고 A의 오른쪽은 틀림없이 A의 오른쪽나무이다
  • 같은 이치로 B가 A인 좌자나무의 뿌리 결점.....
  • 이렇게 귀속하면 확실한 두 갈래 나무를 생성할 수 있다

  • 따라서 두 갈래 트리를 차례로 복원하는 코드를 쓸 수 있습니다.
    #include 
    #include 
    using namespace std;
    
    struct node {
        char data;
        node *left, *right;
        node(char _data): data(_data), left(NULL), right(NULL) {}
    };
    
    int n;  //  
    string preOrder, inOrder;
    
    node *createTree(int preL, int preR, int inL, int inR) {
        if(preL > preR)
            return NULL;
        char nowChar = preOrder[preL];
        node *root = new node(nowChar);
        int pos = inOrder.find(nowChar);
        int len = pos - inL;    //  
        root->left = createTree(preL + 1, preL + len, inL, pos - 1);
        root->right = createTree(preL + len + 1, preR, pos + 1, inR);
        return root;
    }
    
    int getHeight(node *root) {
        if(root == NULL)
            return 0;
        else
            return max(getHeight(root->left), getHeight(root->right)) + 1;
    }
    
    int main()
    {
        cin >> n >> preOrder >> inOrder;
        node *root = createTree(0, preOrder.size()-1, 0, inOrder.size() - 1);
        printf("%d", getHeight(root));
        return 0;
    }
    

    좋은 웹페이지 즐겨찾기