如何将双向链表转换为二叉树

Question

    struct cnode
{
  int info;
  struct cnode *next;
  struct cnode *previous;
};
typedef struct cnode cnode;

预制双向链表：1<->2<->3<->4<->5<->6<->7

因此，我尝试创建一个递归函数，该函数获取双向链表(root = 4)的中间部分，并将其转换为剩余部分，再转换为二叉树。我对递归仍然是个新手，所以如果能给我讲解和代码，我将不胜感激！

EX.     4
      /  \
     2    6
    / \  / \
   1   3 5  7

这就是我到目前为止拥有的代码(由于递归的困难，这并不是很多)

void *convert(cnode *head){
  if(head == NULL)
    return;
  int count = 0;
  cnode *tempHead = head;
  while(tempHead != NULL){
    count++;
    tempHead = tempHead->next;
  }
  int move = (count/2) + (count%2);
  int i;
  for(i=1; i<move; i++){
    head = head->next;
  }
}

几乎只是将头指针设置为mid信息(4)

Answer 1

我想我明白了；您正在从cnode创建一棵平衡的二叉树，并将previous和next指针重用于左子树和右子树。

..。这就是你的算法。

• 找到二叉树的中间节点(你已经做过了)。
• 把左边的一半变成了二叉树。左半部分是原始头，最后一个元素(中间->上半部分)现在的下半部分指针为NULL。将这左半部分链接到middle->previous (被劫持为sub-tree).
• Turn
• )将右半部分链接到二叉树中；这是以middle->next.为头的元素要使它成为middle->next.
• You的新值，必须保持原始头，因为指向左sub-tree.
• You'll的指针希望您的例程返回二叉树的根，这样上一次调用就可以将它链接到上面的级别。
• 你仍然需要选择一个终止条件，比如头指针是NULL.

这会让你转向解决方案吗？

Answer 2

我希望这段代码能对你有所帮助。使用双向链表的头部调用DLL2BT方法，该方法返回创建的树的根节点。

class box
{
    int data;
    box left=null,right=null;
    box(int a)
    {
        data=a;
    }
}

public static box DLL2BT(box head)// head = linked list head
{       
    if(head!=null)
    {
        box node=null;
        try 
        {
            node = findMid(head);
            node.left.right=null;
            node.left=DLL2BT(head);
            node.right.left=null;
            node.right=DLL2BT(node.right);
        }
        catch( Exception e){ }
        return node;
    }
    return null;
}

public static box findMid(box head)
{
    box slow=head,fast=head.right;
    try
    {
        while(fast!=null)
        {
            slow=slow.right;
            fast=fast.right.right;
        }
    }
    catch(Exception e){ }
    return slow;
}

Answer 3

首先，你试图将DLL转换成二叉树，假设DLL是按照你必须生成的二叉树的顺序给出的。请注意，如果您必须创建traversal.Even，您不能仅从inorder BST创建唯一的树，您不能仅使用inorder遍历来创建它。实际上，我认为您正在尝试做的是将其转换为平衡的BST。即便如此，它也不会是独一无二的。

这是算法..

1)获取链表的中间位置并将其设为根。

2)递归地对左半部分和右半部分执行相同的操作。

      a) Get the middle of left half and make it left child of the root           created in step 1.

      b) Get the middle of right half and make it right child of the           root created in step 1.

时间复杂度: O(nLogn)，其中n是链表中的节点数。

但是，如果您在BST中以与在双向链表中出现的顺序相同的顺序插入节点，则可以在O(n)内解决此问题。