如何雙向鏈表轉換爲二進制樹

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

預先做好雙向鏈表：1<->2<->3<->4<->5<->6<->7如何雙向鏈表轉換爲二進制樹

所以我試圖讓，抓住雙向鏈表的中期遞歸函數（根= 4 ）並將其轉換成剩餘的二進制樹。我仍然對遞歸感到陌生，所以對代碼的解釋將非常感謝！

這是代碼我迄今（這是沒有太大由於與遞歸困難）

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; 
    } 
}

差不多就只有將頭指針到中間信息（4）

來源

2016-03-02 david

我想我明白了;你正在製作一個平衡二叉樹cnodes與先前的和接下來的指針被重新用於左右子樹。

...這是你的算法。

找到二叉樹的中間節點（你已經完成了）。
將左半部分變成二叉樹。左半部分是原始頭部，最後一個元素（中間 - >前一個）現在具有下一個 NULL指針。
鏈接這個左半部分中等>以前（劫持爲左子樹）。
將右半部分變成二叉樹;這是由中間>下一個。使其成爲middle-> next的新值。
你原來的頭部保持爲指針，左子樹。
你會想你的日常返回二叉樹的根，所以前面的調用可以將其鏈接到水平之上。
你仍然必須選擇終止條件，如頭指針是NULL。

這是否讓你移動到一個解決方案嗎？

來源

2016-03-02 23:56:15 Prune

首先，您正在試圖DLL轉換爲二進制樹假設DLL給出的順序，你必須做出二叉樹。請注意，沒有一種獨特的樹可以僅通過中間遍歷來完成。即使必須製作BST，也不能僅通過中間遍歷來製作。我實際上認爲你想要做的是將其轉換成均衡的BST。儘管如此，它也不會是唯一的。
算法如下：
1）獲取鏈表的中間並使其成爲根。
2）對於左半部分和右半部分遞歸地做同樣的事情。
a）獲取左半部分的中間部分，並使其在步驟1中創建的根的左子部分。
b）獲取右半部分的中間部分，並將其作爲步驟1中創建的根的子項。
時間複雜度：O（nLogn）其中n是鏈接列表中的節點數。
雖然如果按照與雙鏈表中顯示的順序相同的順序在BST中插入節點，則可以在O（n）中解決該問題。

來源

2018-01-29 16:56:22 shiwang

如何雙向鏈表轉換爲二進制樹

回答

相關問題