मेरे पास एन प्रथम स्तर के बच्चे नोड्स के साथ पेड़ डेटा संरचना है जिसमें बच्चे भी हैं।पेड़ की अधिकतम गहराई
उदाहरण के लिए:
मैं wou एलडी जानना पसंद है कि किस ब्रैच की सबसे बड़ी गहराई है। पिछले उदाहरण में के रूप में यह
node1 होगा - Node11 - Node111 - Node1111
चार स्तर की गहराई है।
कोई सुझाव?
धन्यवाद!
आपको सभी नोड्स की जांच करनी होगी। कई महीने पहले मैं इस तरह से इस एल्गोरिथ्म कार्यान्वित:
class Node
{
public String Name { get; private set; }
public IList<Node> Childs { get; private set; }
public Node(String name)
{
Name = name;
Childs = new List<Node>();
}
public List<Node> Depth
{
get
{
List<Node> path = new List<Node>();
foreach (Node node in Childs)
{
List<Node> tmp = node.Depth;
if (tmp.Count > path.Count)
path = tmp;
}
path.Insert(0, this);
return path;
}
}
public override string ToString()
{
return Name;
}
}
उदाहरण परीक्षण:
Node node1111 = new Node("Node1111");
Node node111 = new Node("Node111");
Node node11 = new Node("Node11");
Node node12 = new Node("Node12");
Node node1 = new Node("Node1");
Node root = new Node("Root");
Node node2 = new Node("Node2");
Node node21 = new Node("Node21");
Node node211 = new Node("Node211");
root.Childs.Add(node1);
root.Childs.Add(node2);
node1.Childs.Add(node11);
node1.Childs.Add(node12);
node11.Childs.Add(node111);
node111.Childs.Add(node1111);
node2.Childs.Add(node21);
node21.Childs.Add(node211);
List<Node> path = root.Depth;
foreach (Node n in path)
Console.Write(String.Format("{0} - ", n.ToString()));
Console.WriteLine();
Node node2111 = new Node("Node2111");
node2111.Childs.Add(new Node("Node21111"));
node211.Childs.Add(node2111);
path = root.Depth;
foreach (Node n in path)
Console.Write(String.Format("{0} - ", n.ToString()));
Console.WriteLine();
कंसोल आउटपुट:
Root - Node1 - Node11 - Node111 - Node1111 -
Root - Node2 - Node21 - Node211 - Node2111 - Node21111 -
यह लगभग उसी तरह से मैंने किया है, लेकिन मुझे इसे सी – WarmWaffles
में अच्छा समाधान लागू करना था। दो सुझाव सबसे पहले, "गहराई" बुरी तरह से नामित है। यह गहराई वापस नहीं करता है। इसे "PathToDeepestLeaf" कहा जाना चाहिए। दूसरा, गुणों को (1) चीजों के लिए आरक्षित किया जाना चाहिए जो तर्कसंगत _properties_ हैं, जैसे रंग या गहराई, जटिल गणना की गई चीजें जैसे "सबसे कम पत्ते के पथ", (2) चीजें जो गणना करने के लिए बहुत तेज हैं, गति के उसी क्रम पर एक क्षेत्र तक पहुंचने के रूप में। मैं इसे एक विधि बनाऊंगा, संपत्ति नहीं। –
आपके लिए एक चुनौती: पेड़ बहुत गहरा हो सकता है। मान लीजिए कि यह एक हज़ार नोड्स गहरे हैं और इतने सारे रिकर्सन ढेर को उड़ा देंगे। क्या आप इसे * रिकर्सन * के बिना कर सकते हैं? –
सबसे सरल एक ब्रूट फोर्स एल्गोरिदम है जो प्रत्येक पथ को दर्शाता है, पॉइंटर्स को सभी नोड्स में सहेजता है, और गहराई को मापता है। प्रत्येक पथ के लिए जो पिछले पथ से अधिक लंबा है, अन्य सभी पथों को भूल जाओ और केवल सबसे लंबे समय तक याद रखें।
The deepest branch from a node is:
the longest of the respective deepest branches from each child node
prepended with the current node.
पेड़ की गहराई को पहले या चौड़ाई-पहले ट्रैक करें, प्रत्येक नोड को इसकी गहराई को आवंटित करें। उच्चतम गहराई के साथ नोड याद रखें।
उस नोड से रूट पर रिकस्रिवल वापस नेविगेट करें। यह आपको सबसे पुरानी शाखा देता है। एक ही लंबाई के साथ एक से अधिक शाखा हो सकती है।
आप तो अपने पेड़ से अधिक इटरेटर के किसी भी रूप है, तो आप अधिकतम गहराई के लिए एक पूरी तरह से सांसारिक दृष्टिकोण का उपयोग कर सकते हैं।
यहाँ मूर्खतापूर्ण एक लाइनर अधिकतम पहुंच योग्य फाइल सिस्टम यूनिक्स find, awk और tr का उपयोग कर गहराई को खोजने के लिए अवधारणा दिखा रहा है:
find/-depth | tr -dc '/\n' \
| awk '{if (length($0) > max) { max=length($0)}}; END {print max}'
... find इटरेटर है, tr एक डेटा हेरफेर "अनुवाद" है एक वर्णों का एक और सेट में सेट करें (इस मामले में इसका उपयोग एकल वर्ण सेट (/) के पूरक (-c) के पूरक (-c) को -d (हटाएं) के लिए किया जा रहा है। इसलिए यह किसी भी यूनिक्स पूर्ण पथ को केवल/विभाजक में परिवर्तित करता है। वहां से मुझे बस इनपुट की सबसे लंबी लाइन मिलती है ... और यह मेरा परिणाम है।
बेशक यह दृष्टिकोण आपको आपके होमवर्क असाइनमेंट के साथ बहुत मदद नहीं करेगा। लेकिन अवधारणा स्पष्ट होनी चाहिए। :)
क्या यह होमवर्क है? –
@ मॉरन: होमवर्क द्वारा आपका क्या मतलब है? – Vincenzo
आप जानते हैं कि होमवर्क क्या है, है ना? –