展開二進制搜索到單鏈表[C]

二叉搜索樹：

扁平單鏈表：

1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11

我似乎無法想出解決辦法出於某種原因。

我對樹節點的結構：

typedef stuct node { 
    int key; 
    struct node *left; 
    struct node *right; 
} Node;

我有一個函數來創建和分配內存以樹節點：

Node* newNode (int key) { 
    Node *new = malloc (sizeof(Node)); 
    new->left = NULL; 
    new->right = NULL; 
    new->key = key; 
    return new; 
}

我有一個列表節點結構：

typedef struct list { 
    int key; 
    struct list* next; 
} List;

我有一個函數來創建列表節點：

List* newListNode (int key) { 
    List *new = malloc(sizeof(List)); 
    new->key = key; 
    new->next = NULL; 
    return new; 
}

而且我有工作函數來創建二叉查找樹，插入值等，但現在我需要創建一個函數來將樹平鋪到列表中。

List* flattenToLL(Node* root) { 
    ... 
}

我似乎無法弄清楚如何將它扁平化爲一個單獨的鏈表。我已經看到很多其他線程和站點討論將二叉搜索樹轉換爲雙向鏈表或循環鏈表，但沒有關於將值複製到單個鏈接列表中的問題。如果任何人都可以提出建議，我可以如何完成這一點，我會非常感激。這是一個家庭作業的任務，所以如果你還可以提供一個小的解釋來幫助我學習這將是偉大的。

來源

2013-04-11 kyle

查找「中序遍歷」。 – 2013-04-11 02:12:14

@CarlNorum我實際上試圖使用inorder遍歷實現扁平化，但我無法弄清楚要在哪些位置設置列表，以及在哪裏創建新的列表節點。 – kyle 2013-04-11 02:23:04

這是比較簡單的遞歸做：

檢查左側的節點;如果有什麼東西，請將左側展平爲列表＃1
檢查右側的節點;如果有那麼點意思，壓平權列表＃2
創建一個單節點列表＃3與當前節點
串接在訂單號清單1中的關鍵 - >＃3 - >＃ 2
返回拼接列表作爲你的結果

這裏是你如何編寫起來：

List* flattenToLL(Node* root) { 
    List *list1 = (root->left) ? flattenToLL(root->left) : NULL; 
    List *list2 = (root->right) ? flattenToLL(root->right) : NULL; 
    List *list3 = newNode(root->key); 
    // The "middle" list3 cannot be NULL; append list2 to list3 
    list3->next = list2; // If list2 is NULL, it's OK 
    if (!list1) return list3; // Nothing to prepend 
    List *last = list1; 
    while (last->next) last=last->next; // Go to the end of list1 
    last->next = list3; // Append list3+list2 to the end of list1 
    return list1; 
}

來源

2013-04-11 02:23:02 dasblinkenlight

非常感謝您的幫助。我試圖解決它的方式是遠離目標。我甚至沒有考慮製作多個列表節點。 – kyle 2013-04-11 02:35:47

你需要做一箇中序遍歷，將每個元素依次與名單。

這種情況的僞代碼：

def traverse (node, list): 
    if node == NULL: return  # Ignore empty subtrees. 
    traverse (node.left, list) # Do left subtree first. 
    list.append (node.data)  # Then current node. 
    traverse (node.right, list) # Then right subtree. 

list = new List()     # Create empty list. 
traverse (root, list)    # Collapse tree to list.

就是這樣，就這麼簡單，因爲它得到。第1步，處理左側子樹。第2步，添加數據。第3步，處理右側子樹。

唯一的「聰明」位的方式，使代碼簡潔空子樹的正確處理。

記住的是，對於最大效率，附加到鏈接列表可以是相對昂貴的操作，如果指針指向最後一個元件（尾）不某處緩存。這將需要找到要添加的每個元素的尾部，這將會使您的展平算法變成一個O(n²)。

因爲在插入的元素開始鏈表幾乎總是O(1)憑藉其實你必須保持head指針，它往往更有效地做一個反向中序遍歷來代替：

def traverse (node, list): 
    if node == NULL: return  # Ignore empty subtrees. 
    traverse (node.right, list) # Do right subtree first. 
    list.insert (node.data)  # Then current node at list start. 
    traverse (node.left, list) # Then left subtree.

這使平坦化操作保持在O(n)。

來源

2013-04-11 02:23:10 paxdiablo

下面是Java代碼，如果有人感興趣：

public static Node bTreeToLinkedList(TreeNode root) { 
    Node list1 = root.getLeftChild() != null ? bTreeToLinkedList(root.getLeftChild()) : null; 
    Node list2 = root.getRightChild() != null ? bTreeToLinkedList(root.getRightChild()) : null; 
    Node list3 = ll.new Node((int) root.getData()); 

    list3.setNext(list2); 
    if (list1 == null) 
     return list3; 

    Node last = list1; 
    while (last.getNext() != null) 
     last = last.getNext(); 
    last.setNext(list3); 

    return list1; 
}

來源

2014-02-27 05:24:46 mihirk

Why dont you do inorder traversal and add values to list in a way. 

public List<Integer> inorderToList(TreeNode<Integer> node, List<Integer> list) { 
     if(node == null) { 
      return list; 
     } 
     if (node != null) { 
      list = inorderToList(node.getLeft(), list); 
      list.add(node.getValue()); 
      list = inorderToList(node.getRight(), list); 
     } 
     return list; 
    }

來源

2014-08-03 03:00:11 plzdontkillme

抱歉沒有意識到你想在鏈接列表中。對不起，關於 – plzdontkillme 2014-08-03 03:01:18

，我們建立一個鏈表樹中的每個級別和列表添加到列表中的一個載體，我們可以使用recurssion。有了這個解決方案，我們需要跟蹤我們所處的級別，所以如果我們已經有一個鏈接列表用於一個級別，並且我們訪問訪問級別上的一個節點，然後纔可以添加到該列表。

我沒有爲自己的節點類添加任何代碼，因爲它與問題不相關，也沒有內存清理正在演示，但更好的解決方案是使用boost :: shared_ptr來處理清理。

void generateLists(vector<list<node*>* >*& lists, node* root, int level) 
{ 
    //base case 
    if(root == NULL) 
     return; 

    //if we have don't have a linked list at this level so create this 
    if((int)lists->size() == level) 
    { 
     list<node*>* ls = new list<node*>(); 
     ls->push_back(root); 
     lists->push_back(ls); 
    } 
    else 
    { 
     //re-use existing list 
     list<node*>* ls = lists->at(level); 
     if(ls != NULL) 
      ls->push_back(root); 
    } 

    //in order traversal 
    generateLists(lists, root->left, level+1); 
    generateLists(lists, root->right, level+1); 
} 

int main(void) 
{ 
    //create a test binary tree 
    node root(6); 
    node n2(3); 
    node n3(9); 
    node n4(2); 
    node n5(5); 
    node n6(8); 
    node n7(9); 

    root.left = &n2; 
    root.right = &n3; 
    n2.left = &n4; 
    n2.right=&n5; 
    n3.left=&n6; 
    n3.right=&n7; 

    //will hold a vector of lists for each level in the tree 
    vector<list<node*>* >* lists = new vector<list<node*>* >(); 
    int level=0; 
    generateLists(lists, &root, level); 
    vector<list<node*>* >::iterator it; 

    //convert each level in the tree to a single linked list 
    list<node*> flattened; 
    for(it = lists->begin(); it != lists->end(); it++) 
    { 
     list<node*>* linkedList = (*it); 
     list<node*>::iterator itNode; 
     for(itNode = linkedList->begin(); itNode != linkedList->end(); itNode++) 
      flattened.push_back(*itNode); 
    } 

    //output the tree as a linked list 
    list<node*>::iterator itNode; 
    for(itNode = flattened.begin(); itNode != flattened.end(); itNode++) 
     cerr<<(*itNode)->val<<" "; 
}

來源

2015-01-10 13:19:18 gilla07

注意：問題是關於'C' c沒有模板也沒有迭代器。 – wildplasser 2015-01-10 13:28:07

對於問題here也存在非遞歸解決方案。

它給你的O（n）的時間複雜度和O（1）空間複雜度。使用遞歸解決方案，你可以獲得堆棧溢出，例如，你將它應用到它自己的輸出中，以用於大節點集。

來源

2015-03-16 10:54:00 Alexey

private static BSTNode head; 
private static BSTNode tail; 
public static void inorderTraversal(BSTNode node) { 
     if(node.left != null) { 
      inorderTraversal(node.left); 
     } 
     System.out.print(node.data + " "); 
     constructLinkedList(node.data); 
     if(node.right != null) { 
      inorderTraversal(node.right); 
     } 
    } 

public static void constructLinkedList(int data) { 
     if(head == null) { 
      head = new BSTNode(data); 
      head.left = null; 
      tail = head; 
     } else { 
      BSTNode node = new BSTNode(data); 
      tail.right = node; 
      tail.left = null; 
      tail = node; 
     } 
    } 

    public static void linkedListToString() { 
     BSTNode curr = head; 
     StringBuilder sb = new StringBuilder(); 
     sb.append("["); 
     while(curr.right != null) { 
      sb.append(curr.data).append("->"); 
      curr = curr.right; 
     } 
     if(curr.right == null) 
      sb.append(curr.data).append("->NULL"); 
     sb.append("]"); 
     System.out.print(sb.toString()); 

    }

來源

2018-01-20 20:38:34 user525146

展開二進制搜索到單鏈表[C]

回答

相關問題