बेसिक ऐरे [] जावा में पेड़ डेटा-संरचना

Question

यह एक होमवर्क प्रश्न है, इसलिए मैं एक पूर्ण कोड उत्तर नहीं ढूंढ रहा हूं।

मैं एक वर्ग कुत्ता

package lab12; 

import java.io.Serializable; 

public class Dog implements Serializable{ 

    public Dog[] children; 
    public String name; 

    public Dog(String name) 
    { 
     this.name = name; 
    } 

    @Override 
    public String toString() 
    { 
     return name; 
    } 

} 

और एक datafile कि एक सरणी में संग्रहीत अपने बच्चों है कि एक जड़ कुत्ते स्पॉट शामिल दिये गये हैं। मुझे कोड लिखने की ज़रूरत है जो डेटाफाइल खोल सकता है, और उसके बाद पेड़ डेटा संरचना के माध्यम से कदम देख सकता है यह देखने के लिए कि कोई इनपुट नाम रूट (स्पॉट) का वंशज है या नहीं।

मुझे पूरा विश्वास है कि मैं डेटाफाइल खोल सकता हूं। मैं नोड्स बनाने के वाक्यविन्यास के साथ संघर्ष कर रहा हूं जिसमें लिंक के रूप में एक सरणी है। हमारी पाठ्यपुस्तक में केवल बाइनरी पेड़ शामिल हैं, जो या तो बाएं या दाएं से लिंक होते हैं, लेकिन लिंक की एक चर संख्या के लिए नहीं। मुझे एक सामान्य व्यक्ति का एक उदाहरण मिला जो एक सूची दृष्टिकोण का उपयोग करता है।

public class Tree<T> 
{ 
    private Node<T> root; 

    public static class Node<T> 
    { 
     private T data; 
     private Node<T> parent; 
     private List<Node<T>> children; 
    } 

    public Tree(T rootData) 
    { 
     root = new Node<T>(); 
     root.data = rootData; 
     root.children = new ArrayList<Node<T>>(); 
    } 
} 

जब से मैं datafile उपयोग करने के लिए मैं एक कुत्ता [] में बच्चों के भंडारण के अलावा और कुछ करने के लिए नोड की संरचना को बदल नहीं सकते हैं। मुझे बच्चों को स्टोर करने के लिए मूल सरणी का उपयोग करके नोड क्लास का एक उदाहरण नहीं मिल रहा है और मैं ऐसा करने के लिए वाक्यविन्यास नहीं समझ सकता। मुझे लगता है कि इससे सीखने की कोशिश करने से पहले यह जेनेरिक के बिना इसे देखने में मेरी समझ में मदद करेगा।

यहाँ अब तक मेरी कोड है:

package lab12; 

public class DogTree 
{ 
    //Start Inner Class 
    private static class Node 
    { 
     private String name; 
     private Node parent; 
     private Node Dog[] children; //This is where I'm confused 
    } 
    //End Inner Class 

    private Node root; 

    public DogTree() 
    { 
     root = null; 
    } 

    public boolean isDescendant(String name) 
    { 
     return isInSubtree(name, root); 
    } 

    private static boolean isInSubtree(String name, Node subTreeRoot) 
    { 
     if(subTreeRoot == null) 
     { 
      return false; 
     } 
     else if(subTreeRoot.name.equals(name)) 
     { 
      return true; 
     } 
     else 
     { 
      //This is where my confusion on the 
      //node design causes implementation problems 
      return isInSubtree(name, subTreeRoot.children); 
     } 
    } 
} 

Answer 1

आप बच्चों की सरणी पर पुनरावृति की जरूरत है।

private static boolean isInSubtree(String name, Node subTreeRoot) 
    { 
     if(subTreeRoot == null) 
     { 
      return false; 
     } 
     else if(subTreeRoot.name.equals(name)) 
     { 
      return true; 
     } 
     else 
     { 
      for(int i = 0; i< subTreeRoot.children.length();i++) 
      if(isInSubtree(name, subTreeRoot.children[i])) 
      return true; 
     } 
     return false; 

    } 

Answer 2

उन एल्गोरिदम में सरणी और सरणी सूची के बीच मुख्य अंतर आप सरणियों के लिए सीमित क्षमता है और आप के आइटम (पिल्लों) आवंटन को संभालने की ज़रूरत है;

यदि कार्य सरणी सीखना है तो आपको जेनेरिक पर ध्यान केंद्रित नहीं करना चाहिए। जेनेरिक आपको वस्तुओं की सामान्य कार्यक्षमता के लिए टेम्पलेट को परिभाषित करने की अनुमति देता है। कंक्रीट मुद्दे को हल करने के लिए उनसे शुरू होने से सामान्य में किए जाने पर कार्यान्वयन को बेहतर बनाना बेहतर होता है।

क्या आप अब इस तरह वर्ग है:

class Dog { 

    private String name; 
    private Dog[] puppies 

    public Dog(String name) 
    { 
     this.name = name; 
    } 

} 

आप क्या कर सकते यह करने के लिए विशेष विधि को जोड़ने के लिए है कि कुछ कार्य नहीं है।

class Dog { 

    private final String name; 
    private final Dog[] puppies = new Dog[20]; //We create 20 slots for puppies to fill 
    private int puppiesCount = 0; 

    public Dog(String name) 
    { 
     this.name = name; 
    } 

    public addPuppie(Dog puppie) { 
     this.puppies[puppiesCount] = puppie; //We assign the puppie to this Dog puppies. 
     this.puppiesCount = puppiesCount + 1; //We increment the count of puppies 
    } 

    public Dog[] getPuppies() { 
     return Arrays.copyOf(puppies, puppiesCount); 
    } 

    public boolean isMyPuppie(Dog puppie) { 

     for(int = 0; i < puppiesCount; i++) { 

      if(puppies[i] == puppie) { //We compare the object references to state that are equal 
      return true; 
      } 

     } 

     return false; 
    } 
} 

यह एक पेड़ में कैसे स्थानांतरण करता है।

चूंकि प्रत्येक ऑब्जेक्ट में स्वयं की एक सरणी होती है, इसलिए उन्हें घोंसला करना संभव है।

Dog max = new Dog("Max"); 

Dog tom = new Dog("Tom"); //childOfRoot; 

Dog barry = new Dog("Barry);"// child of Tom 

एक पेड़ बनाने के लिए आपको ऐसा कुछ करने की आवश्यकता है।

tom.addPuppie(barry); // We assign barry to tom 
max.addPuppie(tom); // we assign tom to max. 

इस अवधारणा को गहरी खोज जहाँ आप एक पुनरावृतिक खोज और माता पिता के लिए बच्चे से एक रिश्ता जोड़ा जा सकता है शुरू करने की जरूरत है के साथ बढ़ाया जाना चाहिए।