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

进行中序树遍历：httpvisit(node) ://en.wikipedia.org/wiki/Tree_traversal#In-order将节点附加到双向链表的位置。