[자료구조] Program to convert a given binary tree to doubly linked list

Binary tree(이진트리) 란?

-자료를 저장하는 구조의 한 종류로써 하나의 node에 최대 두 개의 children이 좌 우로 존재하는 형태.

 ex)정이진트리, 완전이진트리 등

 

주어진 binary tree를 doubly linked list로 변환하는 코드를 리뷰해보겠습니다.

 

https://www.javatpoint.com/program-to-convert-a-given-binary-tree-to-doubly-linked-list

Program to Convert a Given Binary Tree to Doubly Linked List - javatpoint

원문에서는 in-order traversing 으로 트리를 탐색하고 노드의 각 값을이를 doubly linked list의 tail 부분에 저장하는 방식으로 진행했습니다.

 

*/

in-order : left child -> root -> right child

pre-order : root -> left child -> right child

post-order : left child -> right child -> root

/*

 

binary tree 를 구현하기 위해 아래와 같이 struct를 선언하고.

struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};     

parameter가 NULL이 아닌 경우 함수에 left child를 재귀적으로 호출하고, head 유무를 따져 tail뒤에 값을 저장합니다.

이후 right child를 다시 재귀적으로 호출합니다.

void convertbtToDLL(struct node *node) {  
    //Checks whether node is NULL  
    if(node == NULL)  
        return;  
      
    //Convert left subtree to doubly linked list  
    convertbtToDLL(node->left);  
      
    //If list is empty, add node as head of the list  
    if(head == NULL) {  
        //Both head and tail will point to node  
        head = tail = node;  
    }  
    //Otherwise, add node to the end of the list  
    else {  
        //node will be added after tail such that tail's right will point to node  
        tail->right = node;  
        //node's left will point to tail  
        node->left = tail;  
        //node will become new tail  
        tail = node;  
    }  
      
    //Convert right subtree to doubly linked list  
    convertbtToDLL(node->right);  
}

위와 같은 방법으로 함수를 재귀적으로 호출하게되면,

호출한 함수들이 Stack(LIFO:Last In First Out) 형식으로 실행되어서 결과적으로 의도한 바인 in-order의 순서대로 트리의 각 노드 값이 doubly list에 저장됩니다.

 

예를 들어 위와 같은 트리가 주어졌다고 가정하면, 트리 아래에 있는 doubly list의 형식으로 저장됩니다.

코드를 천천히 따라가며 노트에 적어보시면 이해하기 수월합니다.

 

Ternary tree를 pre-order로 traverse하여 저장하는 경우

*Ternary tree child의 수가 최대 3개

 

이 경우, binary tree와 다른 점은 각 node child의 수이다. pre-order로 traverse하여 doubly linked list에 저장하려고 하면 코드가 어떻게 바뀔지 생각해보자.

struct node{  
    int data;  
    struct node *left;  
    struct node *middle;
    struct node *right;  
};     

child 가 세개인 것을 구현하기 위해 struct에 middle pointer를 추가하고.

 
void convertbtToDLL(struct node *node) {  
    //Checks whether node is NULL  
    if(node == NULL)  
        return;  
 
    //If list is empty, add node as head of the list  
    if(head == NULL) {  
        //Both head and tail will point to node  
        head = tail = node;  
    }  
    //Otherwise, add node to the end of the list  
    else {  
        //node will be added after tail such that tail's right will point to node  
        tail->right = node;  
        //node's left will point to tail  
        node->left = tail;  
        //node will become new tail  
        tail = node;  
    }  
    
  convertbtToDLL(node->left);   

    convertbtToDLL(node->middle); 

    convertbtToDLL(node->right);  
}

pre-order 방식으로 root -> left child -> middle child-> right child 순서로 traverse할 것이기 때문에, 재귀함수를 부르는 부분이 node 값을 저장하는 부분 뒤쪽으로 빠졌다.

 

 

이번에 알아본 tree를 doubly linked list로 변환하는 알고리즘은 재귀함수로 order traversing 을 구현하는 방식을 이해하는 것이 point인 것 같다. 여기서는 호출된 함수들이 stack(LIFO형식)으로 실행된다는 점이 핵심이다.

인상적이었던 점은 binary tree와 doubly linked list가 아래의 struct를 공유할 수 있다는 점이다.

struct node{  
    int data;  
    struct node *left;  
    struct node *right;  
};