list - 二分探索木を双方向リストに変換する方法は?

Question

これは二分探索木です：</p>

今、私はそれを次のような双方向リストに変換したいと思います: 4<->6<->8<->10<->12<->14<->16、どうすればいいですか?

どうも

Answer 1

ツリーを順不同でトラバーサルし、データをリストに挿入できます。

// 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

順序付けされたツリー トラバーサルを実行します: http://en.wikipedia.org/wiki/Tree_traversal#In-order ノードvisit(node)を二重リンク リストに追加します。