रिकर्सिव बाइनरी सर्च ट्री

Question

तो यह मेरा पहला जावा प्रोग्राम है, लेकिन मैंने कुछ वर्षों तक सी ++ किया है। मैंने लिखा जो मुझे लगता है कि काम करना चाहिए, लेकिन वास्तव में यह नहीं करता है। तो मैं इस कॉल के लिए एक विधि लिखने के लिए होने की एक शर्त थी:

tree.insertNode(value); 

जहां मूल्य एक पूर्णांक है। मैं इसे रिकर्सिवली लिखने के लिए, स्पष्ट कारणों के लिए चाहता था, इसलिए मैं चारों ओर एक काम करने के लिए किया था:

public void insertNode(int key) { 
    Node temp = new Node(key); 

    if(root == null) root = temp; 

    else insertNode(temp); 
} 

public void insertNode(Node temp) { 
    if(root == null) 
     root = temp; 

    else if(temp.getKey() <= root.getKey()) 
     insertNode(root.getLeft()); 

    else insertNode(root.getRight()); 
} 

किसी भी सलाह के लिए धन्यवाद।

Answer 1

आप एक नया ऑब्जेक्ट प्रकार Node बनाने के बजाय मानक Integer (आदिम int के लिए रैपर) ऑब्जेक्ट का उपयोग कर सकते हैं। नवीनतम जावा इंटीजर/int ऑटो-मुक्केबाजी पर समर्थित है। इसलिए आपकी विधि insertNode(int key)Integer तर्क भी ले सकती है (सुनिश्चित करें कि यह शून्य नहीं है)।

संपादित करें: Pls टिप्पणी के ऊपर अनदेखा करें। मैं आपका असली सवाल नहीं समझ पाया। आपको insertNode() अधिभारित करना होगा। मेरे विचार से आप सही है।

Answer 2

लेकिन जब आप insertNode पर temp कहां है ?? यदि रूट शून्य नहीं है तो आपके वर्तमान कार्यान्वयन के साथ अस्थायी खो गया है।

मुझे लगता है कि आप की तरह

root.getLeft().insertNode(temp); 

और

root.getRight().insertNode(temp); 

कुछ चाहते हैं यानी बाएं या दाएं सबट्री नया नोड (अस्थायी) सम्मिलित करने के लिए।

Answer 3

कोड अधिभारित कार्यों के साथ थोड़ा उलझन में दिखता है। मान लिया जाये कि सदस्य चर 'छोड़' और 'सही' बाईं बच्चे और BSTree के अधिकार के बच्चे क्रमशः होने के लिए, आप निम्नलिखित तरीके से लागू करने की कोशिश कर सकते हैं:

public void insert(Node node, int value) { 
    if (value < node.value) 
    { 
     if (node.left != null) 
     { 
      insert(node.left, value); 
     } 
     else 
     {  
      node.left = new Node(value); 
     } 
    } 
    else if (value > node.value) 
    { 
     if (node.right != null) 
     { 
      insert(node.right, value); 
     } 
     else 
     { 
      node.right = new Node(value); 
     } 
    } 
} 

........ 
public static void main(String [] args) 
{ 
    BSTree bt = new BSTree(); 
    Node root = new Node(100); 
    bt.insert(root, 50); 
    bt.insert(root, 150); 
} 

Answer 4

// In java it is little trickier as objects are passed by copy. 
// PF my answer below. 

// public calling method 

public void insertNode(int key) { 
    root = insertNode(root, new Node(key)); 
} 

// private recursive call 

private Node insertNode(Node currentParent, Node newNode) { 

    if (currentParent == null) { 
     return newNode; 
    } else if (newNode.key > currentParent.key) { 
     currentParent.right = insertNode(currentParent.right, newNode); 
    } else if (newNode.key < currentParent.key) { 
     currentParent.left = insertNode(currentParent.left, newNode); 
    } 

    return currentParent; 
} 

समीर सुकुमारन

Answer 5

आपको इस लेख को देखना चाहिए। http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

// This method mainly calls insertRec() 
void insert(int key) { 
    root = insertRec(root, key); 
} 

/* A recursive function to insert a new key in BST */ 
Node insertRec(Node root, int key) { 

    /* If the tree is empty, return a new node */ 
    if (root == null) { 
     root = new Node(key); 
     return root; 
    } 

    /* Otherwise, recur down the tree */ 
    if (key < root.key) 
     root.left = insertRec(root.left, key); 
    else if (key > root.key) 
     root.right = insertRec(root.right, key); 

    /* return the (unchanged) node pointer */ 
    return root; 
}