查找C＃中節點的深度＃

我有一個未排序的對象列表。這些對象表示一棵二叉樹。查找C＃中節點的深度＃

對象的列表：

new List<Object> 
{ 
    new { Id = 3, Left = /, Right =/} 
    new { Id = 5, Left = /, Right =/} 
    new { Id = 4, Left = 2, Right = 5 } 
    new { Id = 2, Left = 1, Right = 3 } 
    new { Id = 1, Left = /, Right =/} 
}

二叉樹：

我需要一種算法，會發現這些節點的深度。我知道的唯一算法是深度優先搜索。這意味着我必須將對象列表轉換爲樹。考慮到.NET沒有明確的樹形數據結構，你會如何解決這個問題？我是否必須將數據結構轉換爲樹（我不是真的想寫所有的代碼）。還有其他算法嗎？

來源

2010-11-17 Martin

int nodeToFind = 2; 
var currentNode = list.Single(n => n.Id == nodeToFind); 
int depth = 0; 
while ((currentNode = list 
    .FirstOrDefault(i => i.Left == currentNode.Id || i.Right == currentNode.Id)) != null) 

    depth++; 
Console.WriteLine(depth);

簡單但效率低下。

來源

2010-11-17 22:41:33

您可以將您的對象添加到字典中，使用每個左側和右側值作爲關鍵字並將Id作爲值（基本上是反向映射）。然後你寫這樣的遞歸函數...

Dictionary<int, int> map; 
    int depth(int node) 
    { 
     if (!map.ContainsKey(node)) 
      return 0; 
     return depth(map[node]) + 1; 
    }

來源

2010-11-17 22:45:22 tbischel

你可以只是做一個Dictionary<int,int> parents。將節點ID存儲爲密鑰，並將節點的父節點存儲爲值。請注意，這意味着要在原始列表中的每個對象的字典中存儲零個，一個或兩個記錄。然後，要查找節點的深度，只需計算在用完之前您可以獲得父節點的次數。類似這樣的：

public static int NodeDepth(int node, Dictionary<int,int> parents) 
{ 
    int depth = 0; 
    while (parents.ContainsKey(node)) 
    { 
      node = parents[node]; 
      depth++; 
    } 
    return depth; 
}

來源

2010-11-17 22:48:45

查找C＃中節點的深度＃

回答

相關問題