बाइनरी ट्री सम्मिलित करें एल्गोरिदम

Question

मैंने हाल ही में एक परियोजना के लिए एक बाइनरी खोज पेड़ को कार्यान्वित करना समाप्त कर दिया था जिस पर मैं काम कर रहा था। यह अच्छी तरह से चला गया और मैंने बहुत कुछ सीखा। हालांकि, अब मुझे एक नियमित बाइनरी ट्री लागू करने की जरूरत है ... जो किसी कारण से मुझे स्टंप कर दिया गया है।

मैं अपने InsertNode समारोह करने के लिए एक रास्ता तलाश कर रहा हूँ ..

सामान्य रूप से एक BST में आप सिर्फ अगर डेटा < जड़ तो छोड़ दिया डालने और इसके विपरीत की जाँच करें। हालांकि, एक सामान्य बाइनरी पेड़ में, यह सिर्फ बाएं से दाएं, एक समय में एक स्तर से भरा हुआ है ..

कोई भी मुझे ऐसे फ़ंक्शन को लागू करने में मदद कर सकता है जो बाइनरी पेड़ में बाएं से दाएं तक एक नया नोड जोड़ता है कोई विशिष्ट आदेश नहीं है?

void Insert(Node *& root, int data) 
{ 
    if(root == nullptr) 
    { 
    Node * NN = new Node; 
    root = NN; 
    } 
    else 
    { 
    if(data < root->data) 
    { 
     Insert(root->left, data); 
    } 
    else 
    { 
     Insert(root->right, data); 
    } 
    } 
} 

Answer 1

आप, जैसे एक्स = नई (एक्स) एक पुनरावर्ती दृष्टिकोण का उपयोग करता है, तो आप जानते हैं कि क्या मतलब है की कोशिश करनी चाहिए:

यहाँ एक BST के लिए मेरे सम्मिलित है। इस तरह, आपको रूट नोड के बारे में चिंता करने की ज़रूरत नहीं है। मैं तुम्हारे लिए कुछ स्यूडोकोड लिखने के लिए जा रहा हूँ:

//public function 
add(data){ 
    root = add(data, root) 
} 

//private helper function 
Node add(data, currentNode){ 
    if(currentNode = 0) 
     return new Node(data) 

    if(data less than currentNode's data) 
     currentNode.left = add(data, currentNode.left) 
    if(data more than currentNode's data) 
     currentNode.right = add(data, currentNode.right) 

    return currentNode  
} 

मैं सी ++ में एक BST के कार्यान्वयन के बारे में एक ट्यूटोरियल बनाया है, here

Answer 2

मैं इस तथ्य यह एक सवाल कुछ समय पहले तैनात है कि के बारे में पता कर रहा हूँ , लेकिन मैं अभी भी इस पर अपने विचार साझा करना चाहता था।

मैं क्या करूंगा (क्योंकि यह वास्तव में बहुत अच्छी तरह से प्रलेखित नहीं है) एक ब्रेडथ-फर्स्ट-सर्च (कतार का उपयोग करके) का उपयोग करता है और बच्चे को पहली बार मुठभेड़ में डाल देता है। यह सुनिश्चित करेगा कि आपका पेड़ दूसरे स्तर पर जाने से पहले स्तर को भर देगा। नोड्स की सही संख्या के साथ, यह हमेशा पूरा हो जाएगा।

मुझे लगता है कि सी के साथ बहुत काम किया है नहीं ++, तो यकीन है कि यह सही मैं जावा में ऐसा किया था हो सकता है, लेकिन आप अंदाजा हो:

public void insert(Node node) { 
    if(root == null) { 
     root = node; 
     return; 
    } 

    /* insert using Breadth-first-search (queue to the rescue!) */ 
    Queue<Node> queue = new LinkedList<Node>(); 
    queue.offer(root); 

    while(true) { 
     Node n = queue.remove(); 
     if(!n.visited) System.out.println(n.data); 
     n.visited = true; 

     if(n.left == null) { 
      n.left = node; 
      break; 
     } else { 
      queue.offer(n.left); 
     }   

     if(n.right == null) { 
      n.right = node; 
      break; 
     } else { 
      queue.offer(n.right); 
     } 
    } 
} 

Answer 3

मैं bknopper कोड ले लिया है, एक छोटा सा संशोधन किया और सी ++ में अनुवाद किया गया। जैसा कि उन्होंने कहा, आश्चर्य की बात है, यह अच्छी तरह से प्रलेखित नहीं है।

struct nodo 
{ 
    nodo(): izd(NULL), der(NULL) {}; 
    int val; 
    struct nodo* izd; 
    struct nodo* der; 
}; 

void inserta(struct nodo** raiz, int num) 
{ 

if(!(*raiz)) 
{ 
    *raiz = new struct nodo; 
    (*raiz)->val = num; 
} 
else 
{ 

    std::deque<struct nodo*> cola; 
    cola.push_back( *raiz ); 

    while(true) 
    { 
     struct nodo *n = cola.front(); 
     cola.pop_front(); 

     if(!n->izd) { 
      n->izd = new struct nodo; 
      n->izd->val = num; 
      break; 
     } else { 
      cola.push_back(n->izd); 
     } 

     if(!n->der) { 
      n->der = new struct nodo; 
      n->der->val = num; 
      break; 
     } else { 
      cola.push_back(n->der); 
     } 
    } 
    } 
} 

आप इसे इस तरह कहते हैं: inserta(&root, val);

होने के नाते जड़ struct और वैल पूर्णांक मान आप सम्मिलित करना चाहते नोड के लिए एक सूचक

यहाँ नोड संरचना और डालने कार्य है।

उम्मीद है कि यह किसी की मदद करेगा।

Answer 4

अपने कोड में कुछ संशोधनों के साथ

, मुझे आशा है कि यह मदद करनी चाहिए:

Node * Insert(Node * root, int data) 
{ 
    if(root == nullptr) 
    { 
    Node * NN = new Node(); 
    root = NN; 
    root->data = data; 
    root->left = root ->right = NULL; 

    } 
    else 
    { 
    if(data < root->data) 
    { 
     root->left = Insert(root->left, data); 
    } 
    else 
    { 
     root->right = Insert(root->right, data); 
    } 
    } 
    return root; 
} 

इसलिए, इस समारोह अद्यतन BST का रूट नोड देता है।

Answer 5

Javascript क्रियान्वयन (अपने वेब कंसोल के लिए तैयार कॉपी-पेस्ट):

ES6 कार्यान्वयन (वर्ग खोजशब्द के साथ नए Javscript वाक्य रचना)

class BinaryTree { 
     constructor(value){ 
      this.root = value; 
      this.left = null; 
      this.right = null; 
     } 

     insert(value){ 
      var queue = []; 
      queue.push(this); //push the root 
      while(true){ 
       var node = queue.pop(); 
       if(node.left === null){ 
        node.left = new BinaryTree(value); 
        return; 
       } else { 
        queue.unshift(node.left) 
       } 

       if(node.right === null){ 
       node.right = new BinaryTree(value); 
       return; 
       } else { 
       queue.unshift(node.right) 
       } 
      } 
     } 
    } 

    var myBinaryTree = new BinaryTree(5); 
    myBinaryTree.insert(4); 
    myBinaryTree.insert(3); 
    myBinaryTree.insert(2); 
    myBinaryTree.insert(1); 

    5 
/ \ 
    4  3 
/\ (next insertions here) 
2 1  

Pseudoclassical पैटर्न कार्यान्वयन

var BinaryTree = function(value){ 
    this.root = value; 
    this.left = null; 
    this.right = null; 
    } 

    BinaryTree.prototype.insert = function(value){ 
    //same logic as before 
    }