हम BST में नए नोड को रिकर्सिव तरीके से डाल सकते हैं। उस मामले में हम प्रत्येक सबट्री के रूट का पता लौटाते हैं। यहां हम एक और दृष्टिकोण देखेंगे, जहां पैरेंट पॉइंटर को बनाए रखने की आवश्यकता होगी। पैरेंट पॉइंटर किसी नोड के पूर्वज को ढूंढने में मददगार होगा।
विचार बाएं और दाएं सबट्री के पते को संग्रहीत करना है, हम रिकर्सिव कॉल के बाद लौटाए गए पॉइंटर्स के पैरेंट पॉइंटर्स सेट करते हैं। यह पुष्टि करता है कि इंसर्शन के दौरान सभी पैरेंट पॉइंटर्स सेट हैं। रूट का पैरेंट NULL पर सेट है।
एल्गोरिदम
insert(node, key) -
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
