이진 검색 트리를 양방향 목록으로 변환하는 방법은 무엇입니까?

Question

이 이진 검색 트리입니다 :

가 지금은이 같은 양방향 목록에 변환 할 : 4 < -> 6 < -> 8 < -> 10 < -> 12 < -> 14 < -> 16 어떻게 할 수 있습니까?

Answer 1

트리의 inorder 순회를 수행하고 목록에 데이터를 삽입 할 수 있습니다.

// Doubly linked list structure 
typedef struct node 
{ 
    int data; 
    struct node *prev; 
    struct node *next; 
}list; 

// Create node 
list* createnode(int x) 
{ 
    list* temp=(list*)malloc(sizeof(list)); 
    temp->data=x; 
    temp->prev=NULL; 
    temp->next=NULL; 
    return temp; 
} 

list *head=NULL; // To keep track of head 
list *ptr=NULL; //To keep track of last pointer in list 
Inorder(tree * root) 
{ 
    if(root==NULL) return; 
    Inorder(root->left); 
    // Insert head node 
    if(head==NULL) 
    { 
     head=createnode(root->data); 
     ptr=head; 
    } 
    // Insert other nodes and provide links 
    else 
    { 
     list *temp=createnode(root->data); 
     ptr->next=temp; 
     temp->prev=ptr; 
     ptr=temp; 
    } 
    Inorder(root->right); 
} 

Answer 2

들으 중위 트리 탐색을 수행 visit(node)http://en.wikipedia.org/wiki/Tree_traversal#In-order는 이중 연결리스트에 노드를 추가한다.