1. 홈
  2. 질의 응답
  3. 선주문 (기본)으로 BST를 DLL로 변환

선주문 (기본)으로 BST를 DLL로 변환

2017-12-16 3 views
-1

나는 BST를 보유하고 있으며이를 선주문 기반의 양방향 연결 목록으로 만들어야합니다. 이 함수는 왼쪽 포인터가 목록의 이전 멤버를 가리키고 오른쪽 포인터가 다음 포인터를 가리 키도록 트리의 각 노드의 포인터를 변경해야합니다. (루트의 이전 (왼쪽)은 NULL이고 마지막 노드 (오른쪽)의 다음과 마찬가지로 NULL입니다.) 목록을 인쇄하려면 생성 된 DLL의 헤드를 반환해야합니다.선주문 (기본)으로 BST를 DLL로 변환

장애물 : 보조 기능을 사용할 수 없으며 트리 자체의 포인터를 변경하고 새 목록을 만들어야합니다. 구현은 C.에 여기 

 4        
    / \  
    2  6 ---------> output of DLL: 4<->2<->1<->3<->6<->5<->7.   
/\ /\       
1 3 5 7

내 코드입니다; 누군가가 나를 도울 수 있기를 바랍니다. 

Node* converToPreOrder(Node* root) 
{ 
    if (root == NULL) return root; 

    static Node* head = NULL; 
    static Node* prev = NULL; 
    Node* temp = root; 

    if (prev == NULL) 
     head = root; 

    if (root->right != NULL && root->left != NULL) 
     prev = root; 

    else 
    { 
     prev->right = root; 
     temp->left = prev; 
    } 

    converToPreOrder(root->left); 
    converToPreOrder(root->right); 

    return head; 
}

출처

2017-12-16 Daniel Mirz

+1

스택 오버플로에 오신 것을 환영합니다. 곧 [About] 및 [Ask] 페이지를 읽으십시오. 코드를 실행 했습니까? 어떤 대답을 얻었습니까? BST가 올바르게 구조화되었음을 어떻게 입증 했습니까? 어떻게 당신이 일관된 DLL을 가지고 있다는 것을 증명합니까? 이것들은 MCVE ([MCVE])의 측면입니다. - 어떤 상황에서'if (prev == NULL) head = root;의 지정이 실행되지 않을 것이라고 생각하십니까? 왜 단순히 '머리'를 초기화하지 않았습니까? –

답변

1

다음은 작동하는 코드입니다. 변환 기능은 개념이 매우 단순하지만 세부 사항을 처리 할 때 약간의주의가 필요합니다.

  • 현재 노드 (루트) 왼쪽 자녀
  • 목록 :이 문제에 대한

    , 당신이 어떤 주어진 노드를 처리 할 때, 당신은 세 가지 요소를 얻을 필요가 날 것으로 보인다
  • (또한 재귀 생성) 우측 아이리스트

을 (재귀 생성 한), 결과리스트가 있어야 :

  • 우측 아이에 대해리스트 하였다
  • 좌측 아이에 대해리스트 하였다
    • 현재 노드.

    • 질문에서 트리 주어 : 

     4        
    / \  
    2  6 ---------> output of DLL: 4<->2<->1<->3<->6<->5<->7.   
/\ /\       
1 3 5 7

    최종 결과는 다음 노드 (6)로부터리스트이어서 노드 (2)로부터리스트 다음

    • 노드 4,.

    물론, 노드 2의 목록은 다음과 같습니다

    노드 3
  • 노드 1 및 노드 3은 사소한에서 나열되므로 결과로부터리스트이어서 노드 (1)로부터리스트 다음 5,
    • 노드 2이다 :
      • 노드 2 노드 (6)로부터 노드 1, 노드 3

    과 마찬가지로 목록이다 :

    • 노드 6, 노드 5의 목록 다음에 노드 7의 목록이옵니다.결과가되도록
      • 노드 5 및 노드 7에서 그룹, 사소한 :
    • 노드 6, 노드 5, 노드 7

    따라서 최종 결과이다

    • 노드 4, 노드 2, 노드 1, 노드 3, 노드 6, 노드 5, 노드 7
    ,

    목록은 이중 연결되고 널 종료됩니다. 즉, 상기 호출 프로세싱 노드 (4)로 돌아 왔을 때, 왼쪽에서 조직을 갖는 것을 의미한다 :

     +--------+  +--------+  +--------+ 
0 <----|  |<----|  |<----|  | 
     | Node 2 |  | Node 1 |  | Node 3 | 
     |  |---->|  |---->|  |----> 0 
     +--------+  +--------+  +--------+

    사소한 경우는 다음과 이전 널 포인터리스트를 반환한다. 오른쪽 목록에는 노드 6, 5, 7의 순서와 비슷한 구성이 있습니다. 최종 결과를 조립하려면 노드 4의 왼쪽 포인터를 null로 설정하고 노드 4의 오른쪽 포인터를 왼쪽 목록의 머리글로 설정하고 왼쪽 목록 머리의 왼쪽 포인터를 노드 4로 설정하고 노드 4의 우측 포인터로부터 시작하여 우측리스트를 추가하고 우측리스트의 헤드의 좌측 포인터를 우측리스트를 포인팅하는 노드의 우측 포인터로 설정함으로써 행해진 다.

    왼쪽 목록이나 오른쪽 목록 또는 둘 모두가 비어있을 수 있습니다. 이들은 약간의 치료가 필요합니다.

    결과 코드는 3 가지 테스트 케이스로 구성됩니다. 탐색 목록에 대한 노드 기술 포인터의 포인터는 다소 강력하고 가치가 있습니다. 당신은 같은 기술에 대한 다른 SO 질문을 찾을 수 있습니다 print_node() 기능 (Mac에서 실행에 조정되어 

    /* SO 4784-9166 */ 
#include <inttypes.h> 
#include <stdio.h> 

typedef struct Node Node; 
struct Node 
{ 
    int number; 
    Node *left; 
    Node *right; 
}; 

static Node *convertToPreOrder(Node *root) 
{ 
    if (root == 0) 
     return 0; 
    Node *l_list = convertToPreOrder(root->left); 
    Node *r_list = convertToPreOrder(root->right); 
    root->left = 0; 
    /* Add left list */ 
    root->right = l_list; 
    if (l_list != 0) 
     l_list->left = root; 
    /* Find the end */ 
    Node **pos = &root; 
    while ((*pos)->right != 0) 
     pos = &(*pos)->right; 
    /* Add right list */ 
    (*pos)->right = r_list; 
    if (r_list != 0) 
     r_list->left = *pos; 
    return root; 
} 

static void print_node(Node *node) 
{ 
    if (node != 0) 
     printf("Node = 0x%.12" PRIXPTR " - Number = %d - " 
       "Left = 0x%.12" PRIXPTR " - Right = 0x%.12" PRIXPTR "\n", 
       (uintptr_t)node, node->number, (uintptr_t)node->left, (uintptr_t)node->right); 
} 

static void print_BST_preorder(Node *root) 
{ 
    if (root == 0) 
     return; 
    print_node(root); 
    print_BST_preorder(root->left); 
    print_BST_preorder(root->right); 
} 

static void print_list(Node *list) 
{ 
    while (list != 0) 
    { 
     print_node(list); 
     list = list->right; 
    } 
} 

static Node *add_bst_node(Node *root, Node *node) 
{ 
    if (root == 0) 
     return node; 
    if (node->number >= root->number) 
     root->right = add_bst_node(root->right, node); 
    else 
     root->left = add_bst_node(root->left, node); 
    return root; 
} 

static void test_bst_to_list(size_t n_nodes, Node nodes[]) 
{ 
    Node *root = 0; 
    for (size_t i = 0; i < n_nodes; i++) 
     root = add_bst_node(root, &nodes[i]); 
    printf("Print BST in pre-order:\n"); 
    print_BST_preorder(root); 
    printf("Convert to list\n"); 
    Node *list = convertToPreOrder(root); 
    printf("Print list:\n"); 
    print_list(list); 
    putchar('\n'); 
} 

int main(void) 
{ 
    Node array1[] = 
    { 
     { 4, 0, 0 }, 
     { 2, 0, 0 }, 
     { 1, 0, 0 }, 
     { 3, 0, 0 }, 
     { 6, 0, 0 }, 
     { 5, 0, 0 }, 
     { 7, 0, 0 }, 
    }; 
    enum { ARRAY1_SIZE = sizeof(array1)/sizeof(array1[0]) }; 
    test_bst_to_list(ARRAY1_SIZE, array1); 

    Node array2[] = 
    { 
     { 19, 0, 0 }, 
     { 21, 0, 0 }, 
     { 20, 0, 0 }, 
     { 18, 0, 0 }, 
     { 22, 0, 0 }, 
     { 24, 0, 0 }, 
     { 17, 0, 0 }, 
     { 16, 0, 0 }, 
     { 23, 0, 0 }, 
     { 27, 0, 0 }, 
     { 26, 0, 0 }, 
     { 25, 0, 0 }, 
    }; 
    enum { ARRAY2_SIZE = sizeof(array2)/sizeof(array2[0]) }; 
    test_bst_to_list(ARRAY2_SIZE, array2); 

    Node array3[] = 
    { 
     { 16, 0, 0 }, 
     { 11, 0, 0 }, 
     { 21, 0, 0 }, 
     { 10, 0, 0 }, 
     { 22, 0, 0 }, 
     { 22, 0, 0 }, 
     { 21, 0, 0 }, 
     { 27, 0, 0 }, 
     { 27, 0, 0 }, 
     { 20, 0, 0 }, 
     { 22, 0, 0 }, 
     { 17, 0, 0 }, 
     { 12, 0, 0 }, 
    }; 
    enum { ARRAY3_SIZE = sizeof(array3)/sizeof(array3[0]) }; 
    test_bst_to_list(ARRAY3_SIZE, array3); 

    return 0; 
}

    64 비트에서), 여기서 메모리 주소는 일반적으로 처음 네 개의 nybbles에서 선두가 0인데, 따라서 12 진수로 인쇄하면 충분합니다.

    샘플 출력 :

    Print BST in pre-order: 
Node = 0x7FFEE6F5B180 - Number = 4 - Left = 0x7FFEE6F5B198 - Right = 0x7FFEE6F5B1E0 
Node = 0x7FFEE6F5B198 - Number = 2 - Left = 0x7FFEE6F5B1B0 - Right = 0x7FFEE6F5B1C8 
Node = 0x7FFEE6F5B1B0 - Number = 1 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B1C8 - Number = 3 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B1E0 - Number = 6 - Left = 0x7FFEE6F5B1F8 - Right = 0x7FFEE6F5B210 
Node = 0x7FFEE6F5B1F8 - Number = 5 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B210 - Number = 7 - Left = 0x000000000000 - Right = 0x000000000000 
Convert to list 
Print list: 
Node = 0x7FFEE6F5B180 - Number = 4 - Left = 0x000000000000 - Right = 0x7FFEE6F5B198 
Node = 0x7FFEE6F5B198 - Number = 2 - Left = 0x7FFEE6F5B180 - Right = 0x7FFEE6F5B1B0 
Node = 0x7FFEE6F5B1B0 - Number = 1 - Left = 0x7FFEE6F5B198 - Right = 0x7FFEE6F5B1C8 
Node = 0x7FFEE6F5B1C8 - Number = 3 - Left = 0x7FFEE6F5B1B0 - Right = 0x7FFEE6F5B1E0 
Node = 0x7FFEE6F5B1E0 - Number = 6 - Left = 0x7FFEE6F5B1C8 - Right = 0x7FFEE6F5B1F8 
Node = 0x7FFEE6F5B1F8 - Number = 5 - Left = 0x7FFEE6F5B1E0 - Right = 0x7FFEE6F5B210 
Node = 0x7FFEE6F5B210 - Number = 7 - Left = 0x7FFEE6F5B1F8 - Right = 0x000000000000 

Print BST in pre-order: 
Node = 0x7FFEE6F5B230 - Number = 19 - Left = 0x7FFEE6F5B278 - Right = 0x7FFEE6F5B248 
Node = 0x7FFEE6F5B278 - Number = 18 - Left = 0x7FFEE6F5B2C0 - Right = 0x000000000000 
Node = 0x7FFEE6F5B2C0 - Number = 17 - Left = 0x7FFEE6F5B2D8 - Right = 0x000000000000 
Node = 0x7FFEE6F5B2D8 - Number = 16 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B248 - Number = 21 - Left = 0x7FFEE6F5B260 - Right = 0x7FFEE6F5B290 
Node = 0x7FFEE6F5B260 - Number = 20 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B290 - Number = 22 - Left = 0x000000000000 - Right = 0x7FFEE6F5B2A8 
Node = 0x7FFEE6F5B2A8 - Number = 24 - Left = 0x7FFEE6F5B2F0 - Right = 0x7FFEE6F5B308 
Node = 0x7FFEE6F5B2F0 - Number = 23 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B308 - Number = 27 - Left = 0x7FFEE6F5B320 - Right = 0x000000000000 
Node = 0x7FFEE6F5B320 - Number = 26 - Left = 0x7FFEE6F5B338 - Right = 0x000000000000 
Node = 0x7FFEE6F5B338 - Number = 25 - Left = 0x000000000000 - Right = 0x000000000000 
Convert to list 
Print list: 
Node = 0x7FFEE6F5B230 - Number = 19 - Left = 0x000000000000 - Right = 0x7FFEE6F5B278 
Node = 0x7FFEE6F5B278 - Number = 18 - Left = 0x7FFEE6F5B230 - Right = 0x7FFEE6F5B2C0 
Node = 0x7FFEE6F5B2C0 - Number = 17 - Left = 0x7FFEE6F5B278 - Right = 0x7FFEE6F5B2D8 
Node = 0x7FFEE6F5B2D8 - Number = 16 - Left = 0x7FFEE6F5B2C0 - Right = 0x7FFEE6F5B248 
Node = 0x7FFEE6F5B248 - Number = 21 - Left = 0x7FFEE6F5B2D8 - Right = 0x7FFEE6F5B260 
Node = 0x7FFEE6F5B260 - Number = 20 - Left = 0x7FFEE6F5B248 - Right = 0x7FFEE6F5B290 
Node = 0x7FFEE6F5B290 - Number = 22 - Left = 0x7FFEE6F5B260 - Right = 0x7FFEE6F5B2A8 
Node = 0x7FFEE6F5B2A8 - Number = 24 - Left = 0x7FFEE6F5B290 - Right = 0x7FFEE6F5B2F0 
Node = 0x7FFEE6F5B2F0 - Number = 23 - Left = 0x7FFEE6F5B2A8 - Right = 0x7FFEE6F5B308 
Node = 0x7FFEE6F5B308 - Number = 27 - Left = 0x7FFEE6F5B2F0 - Right = 0x7FFEE6F5B320 
Node = 0x7FFEE6F5B320 - Number = 26 - Left = 0x7FFEE6F5B308 - Right = 0x7FFEE6F5B338 
Node = 0x7FFEE6F5B338 - Number = 25 - Left = 0x7FFEE6F5B320 - Right = 0x000000000000 

Print BST in pre-order: 
Node = 0x7FFEE6F5B350 - Number = 16 - Left = 0x7FFEE6F5B368 - Right = 0x7FFEE6F5B380 
Node = 0x7FFEE6F5B368 - Number = 11 - Left = 0x7FFEE6F5B398 - Right = 0x7FFEE6F5B470 
Node = 0x7FFEE6F5B398 - Number = 10 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B470 - Number = 12 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B380 - Number = 21 - Left = 0x7FFEE6F5B428 - Right = 0x7FFEE6F5B3B0 
Node = 0x7FFEE6F5B428 - Number = 20 - Left = 0x7FFEE6F5B458 - Right = 0x000000000000 
Node = 0x7FFEE6F5B458 - Number = 17 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B3B0 - Number = 22 - Left = 0x7FFEE6F5B3E0 - Right = 0x7FFEE6F5B3C8 
Node = 0x7FFEE6F5B3E0 - Number = 21 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B3C8 - Number = 22 - Left = 0x000000000000 - Right = 0x7FFEE6F5B3F8 
Node = 0x7FFEE6F5B3F8 - Number = 27 - Left = 0x7FFEE6F5B440 - Right = 0x7FFEE6F5B410 
Node = 0x7FFEE6F5B440 - Number = 22 - Left = 0x000000000000 - Right = 0x000000000000 
Node = 0x7FFEE6F5B410 - Number = 27 - Left = 0x000000000000 - Right = 0x000000000000 
Convert to list 
Print list: 
Node = 0x7FFEE6F5B350 - Number = 16 - Left = 0x000000000000 - Right = 0x7FFEE6F5B368 
Node = 0x7FFEE6F5B368 - Number = 11 - Left = 0x7FFEE6F5B350 - Right = 0x7FFEE6F5B398 
Node = 0x7FFEE6F5B398 - Number = 10 - Left = 0x7FFEE6F5B368 - Right = 0x7FFEE6F5B470 
Node = 0x7FFEE6F5B470 - Number = 12 - Left = 0x7FFEE6F5B398 - Right = 0x7FFEE6F5B380 
Node = 0x7FFEE6F5B380 - Number = 21 - Left = 0x7FFEE6F5B470 - Right = 0x7FFEE6F5B428 
Node = 0x7FFEE6F5B428 - Number = 20 - Left = 0x7FFEE6F5B380 - Right = 0x7FFEE6F5B458 
Node = 0x7FFEE6F5B458 - Number = 17 - Left = 0x7FFEE6F5B428 - Right = 0x7FFEE6F5B3B0 
Node = 0x7FFEE6F5B3B0 - Number = 22 - Left = 0x7FFEE6F5B458 - Right = 0x7FFEE6F5B3E0 
Node = 0x7FFEE6F5B3E0 - Number = 21 - Left = 0x7FFEE6F5B3B0 - Right = 0x7FFEE6F5B3C8 
Node = 0x7FFEE6F5B3C8 - Number = 22 - Left = 0x7FFEE6F5B3E0 - Right = 0x7FFEE6F5B3F8 
Node = 0x7FFEE6F5B3F8 - Number = 27 - Left = 0x7FFEE6F5B3C8 - Right = 0x7FFEE6F5B440 
Node = 0x7FFEE6F5B440 - Number = 22 - Left = 0x7FFEE6F5B3F8 - Right = 0x7FFEE6F5B410 
Node = 0x7FFEE6F5B410 - Number = 27 - Left = 0x7FFEE6F5B440 - Right = 0x000000000000

    첫 번째 테스트 케이스 질문에서 샘플 트리에 해당합니다. 트리 구조가 주어지면 노드는 BST 인쇄 W리스트 인쇄에서 동일한 순서로 표시됩니다. 그러나 포인터는 아주 다릅니다. 이 테스트 케이스는 약간의 편의를 위해 너무 단순합니다. BST의 지정된 노드가 비어있는 왼쪽 트리 또는 비어있는 오른쪽 트리 (둘 다 아닌 리프 노드)를 갖는 경우를 테스트하지 않습니다.

    • 출처

    2017-12-18 04:57:11

    관련 문제

     관련 문제