Binary Search Tree Insert ด้วย Parent Pointer ใน C++

เราสามารถแทรกโหนดใหม่เข้า BST แบบ Recursive ได้ ในกรณีนั้นเราจะส่งคืนที่อยู่ของรากของแต่ละ subtree ที่นี่เราจะดูแนวทางอื่น ที่ต้อง maintain parent pointer Parent pointer จะช่วยในการหา ancestor ของโหนด ฯลฯ

แนวคิดคือเก็บที่อยู่ของ left และ right subtrees เราตั้งค่า parent pointers ของ pointers ที่ส่งคืนหลัง recursive call นี่ยืนยันว่า parent pointers ทั้งหมดถูกตั้งค่าระหว่างการแทรก Parent ของ root ถูกตั้งเป็น null

อัลกอริทึม

insert(node, key):

begin
    if node is null, สร้างโหนดใหม่และส่งคืน
    if key < node->data:
        สร้างโหนดใหม่ด้วย key
        เพิ่มโหนดใหม่กับ left pointer ของ node
    else if key >= node->data:
        สร้างโหนดใหม่ด้วย key
        เพิ่มโหนดใหม่ที่ right pointer ของ 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) { // ไป subtree ซ้าย
        Node *left_child = insert(node->left, key);
        node->left = left_child;
        left_child->parent = node;
    } else if (key > node->data) { // ไป 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);
}

ผลลัพธ์