이진 트리 수정

Question

주어진 이진 트리. 수정 후에는 올바른 포인터 만 사용하여 선주문을 순회 할 수있는 방식으로 수정하십시오. 수정하는 동안 왼쪽 포인터뿐만 아니라 오른쪽 포인터를 사용할 수 있습니다.

누군가가 접근 방식을 제안합니까? preorder 대신 inorder를 사용하면 BST로 트리를 수정할 수 있습니다 preorder 대신 postorder traversal을 사용하는 방법에 대한 질문은 어떻게합니까?

Answer 1

이것은 트리를 선형화하는 것입니다. 선주문 순회는 상위 노드, 왼쪽 하위 트리, 오른쪽 하위 트리의 노드를 방문합니다. 오른쪽 포인터 만 사용하여이 작업을 수행하려면 왼쪽 하위 트리가 비어 있어야합니다. 이를위한 아이디어는 하위 트리를 다시 정렬하는 것입니다. 오른쪽 포인터가 원래의 왼쪽 하위 트리를 가리 키도록합니다. 그런 다음이 하위 트리의 마지막 노드의 오른쪽 포인터가 원래의 오른쪽 하위 트리를 가리 키도록합니다. 여기

는 생각이다 : 정직의 관심에서

Node* Linearize(Node* root) // returns the subtree's last node 
{ 
    //if it's a leaf node 
    if(root->left == NULL && root->right == NULL) 
     return root; 

    //if there is no left subtree 
    if(root->left == NULL) 
     return Linearize(root->right); 

    //if there is no right subtree 
    if(root->right == NULL) 
    { 
     root->right = root->left; 
     root->left = NULL; 
     return Linearize(root->right); 
    } 

    //both subtrees exist 
    Node* left = root->left; 
    Node* right = root->right; 
    Node* lastOfLeft = Linearize(left); 
    root->right = left; 
    root->left = NULL; 
    lastOfLeft->right = right; 
    return Linearize(right); 
}