เราสามารถแทรกโหนดใหม่ลงใน 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
