用於將深度數組轉換爲樹的高效算法

我有一個存儲過程，它返回在樹中組織的名稱的平面列表。溝通是誰的人有一個深度值父，所以5條（上升3級）的結果是這樣的：用於將深度數組轉換爲樹的高效算法

Depth|Name 
---------- 
    0|Ford 
    1|Compact Cars 
    2|Pinto 
    1|Trucks 
    2|H-Series

我試圖通過構建一個樹出此陣讀取深度值。有沒有一些明顯的算法來構建一個像這樣的數據序列的樹？我添加了C＃標籤，因爲我對LINQy解決方案對這個問題持開放態度，儘管通用的計算機科學答案會非常有幫助。

這裏是我當前的嘗試：

class Record 
{ 
    public string Name{ get; set; } 
    public List<Record> children { get; set; } 
} 

var previousLevel = 0; 
var records = new List<Record>(); 

foreach (var thing in TreeFactory.fetch(dao)) 
{ 
    if(this.Depth == 0) { 
    //Root node 
    } else if(thing.Depth > previousLevel) { 
    //A Child of the last added node 
    } else if(thing.Depth < previousLevel) { 
    //A Cousin of the last added node 
    } else { 
    //A Sibling of the of the last added node 
    } 
    previousLevel = this.Depth; 
}

通過「高效」我說的是列表尺寸達200,000元，並且一直延伸到100級的樹木，所以真的，我只是希望的東西這更容易推理。

來源

2012-08-27 Jason Sperske

你嘗試過什麼？ –

我目前的代碼從一個簡單的列表開始，其中Record包含名爲Children的列表。然後保留上一個深度的副本並進行測試。如果新深度等於先前它是兄弟姐妹，如果它更大，那麼ti是一個孩子，如果它小於它是最近添加的父親的兄弟姐妹。我說「嘗試」，因爲代碼變得相當混亂。 –

問題的模糊性或者福特汽車的使用是否會因此而被否決？ –

這裏不需要遞歸。我相信，最快的方式是這樣的：

public static TreeView TreeFromArray(Item[] arr) 
{ 
    var tv = new TreeView(); 
    var parents = new TreeNodeCollection[arr.Length]; 
    parents[0] = tv.Nodes; 

    foreach (var item in arr) 
    { 
     parents[item.Depth + 1] = parents[item.Depth].Add(item.Name).Nodes; 
    } 

    return tv; 
}

項目是任何具有深度和名稱信息：

public class Item 
{ 
    public int Depth; 
    public string Name; 
}

當使用我自己的實現樹節點的，簡化的步驟，從剝離它減緩了整個事情下來，改變方法一點點地適應thsoe變化不必要的功能，我想出了這個：

類：

public class Node 
    { 
     public string Name; 
     public List<Node> Childs = new List<Node>(); 
    } 

    public class Item 
    { 
     public int Depth; 
     public string Name; 
    }

實現：

public static Node TreeFromArray(Item[] arr) 
    { 
     var tree = new Node(); 

     var parents = new Node[arr.Length]; 
     parents[0] = tree; 

     foreach (var item in arr) 
     { 
      var curr = parents[item.Depth + 1] = new Node {Name = item.Name}; 
      parents[item.Depth].Childs.Add(curr); 
     } 

     return tree; 
    }

結果：

在給定的數據：100萬次在900毫秒

來源

2012-08-27 17:09:06 SimpleVar

你說需要遞歸，但你的方法不遞歸... – Servy

+1測試:) –

@Servy我說**不需要**，不需要。 – SimpleVar

public void AddNode(Tree tree, Node nodeToAdd, int depth) 
{ 
    //you might need to add a special case to handle adding the root node 
    Node iterator = tree.RootNode; 
    for(int i = 0; i < depth; i++) 
    { 
    iterator = iterator.GetLastChild(); //I assume this method won't exist, but you'll know what to put here 
    } 

    iterator.AddChild(nodeToAdd); 
}

這是有點僞碼-y。它不會添加錯誤處理，並且我假設存在代碼段的方法，我想你可以自己弄清楚。

來源

2012-08-27 17:03:09 Servy

該數組看起來像是一個原始樹結構從左到右的「扁平化」。如果它是安全的假設，那麼方法很簡單：

For each element in the array 
    If the depth of the element is less than or equal to the "current node" 
     traverse upwards to the parent until current depth = element depth -1 
    Create a child node of the current node 
    Traverse to that node as the new "current" node

來源

2012-08-27 17:05:36 KeithS

主料：

類，允許子節點。
此類類型的堆棧。
此類類型的數組或列表。
存儲當前深度的int值。
本地持有我們目前的興趣項目。

方法。

從列表中獲取第一項。把它放在堆棧中。將0作爲當前深度存儲。
從列表中依次取出每個剩餘物品。看看它的深度。如果深度等於或小於當前深度，則從堆棧中彈出（currentdepth - depth + 1）項目，並在堆棧中查看以獲取新的當前項目。使我們的新項目成爲「當前項目」的子項目，使其成爲當前項目，使其深度成爲當前深度。

在200°C或Gas-mark 6下烘烤300毫秒，或直到金黃色。

來源

2012-08-27 17:08:01

用於將深度數組轉換爲樹的高效算法

回答

相關問題