हम पुनरावर्ती तरीके से BST में नया नोड सम्मिलित कर सकते हैं। उस स्थिति में हम प्रत्येक सबट्री की जड़ का पता लौटाते हैं। यहां हम एक और दृष्टिकोण देखेंगे, जहां पेरेंट पॉइंटर को बनाए रखने की आवश्यकता होगी। नोड आदि के पूर्वज को खोजने के लिए पेरेंट पॉइंटर मददगार होगा।
विचार बाएं और दाएं उपट्री के पते को स्टोर करना है, हम रिकर्सिव कॉल के बाद लौटे पॉइंटर्स के पैरेंट पॉइंटर्स सेट करते हैं। यह पुष्टि करता है कि सम्मिलन के दौरान सभी पैरेंट पॉइंटर्स सेट किए गए हैं। रूट का पैरेंट शून्य पर सेट है।
एल्गोरिदम
इन्सर्ट (नोड, की) -
begin if node is null, then create a new node and return if the key is less than the key of node, then create a new node with key add the new node with the left pointer or node else if key is greater or equal to the key of node, then create a new node with key add the new node at the right pointer of the node end if return node end
उदाहरण
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right, *parent;
};
struct Node *getNode(int item) {
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = temp->parent = NULL;
return temp;
}
void inorderTraverse(struct Node *root) {
if (root != NULL) {
inorderTraverse(root->left);
cout << root->data << " ";
if (root->parent == NULL)
cout << "NULL" << endl;
else
cout << root->parent->data << endl;
inorderTraverse(root->right);
}
}
struct Node* insert(struct Node* node, int key) {
if (node == NULL) return getNode(key);
if (key < node->data) { //to the left subtree
Node *left_child = insert(node->left, key);
node->left = left_child;
left_child->parent = node;
}
else if (key > node->data) { // to the right subtree
Node *right_child = insert(node->right, key);
node->right = right_child;
right_child->parent = node;
}
return node;
}
int main() {
struct Node *root = NULL;
root = insert(root, 100);
insert(root, 60);
insert(root, 40);
insert(root, 80);
insert(root, 140);
insert(root, 120);
insert(root, 160);
inorderTraverse(root);
} आउटपुट
40 60 60 100 80 60 100 NULL 120 140 140 100 160 140