Chèn vào cây tìm kiếm nhị phân (BST) với con trỏ cha (Parent Pointer) trong C++

Ta có thể chèn nút mới vào BST theo cách đệ quy, trả về địa chỉ gốc của từng cây con. Ở đây ta dùng cách khác: duy trì con trỏ cha (parent pointer). Con trỏ cha hữu ích để tìm tổ tiên của nút.

Ý tưởng: lưu địa chỉ cây con trái/phải, đặt con trỏ cha của con trỏ trả về sau gọi đệ quy. Điều này đảm bảo tất cả con trỏ cha được thiết lập khi chèn. Con trỏ cha của gốc được đặt là NULL.

Thuật toán

insert(node, key) –

bắt đầu
    nếu node là null, tạo nút mới và trả về
    nếu key < key của node thì
        tạo nút mới với key
        gán nút mới vào con trỏ trái của node
    ngược lại nếu key >= key của node thì
        tạo nút mới với key
        gán nút mới vào con trỏ phải của node
    kết thúc nếu
    trả về node
kết thúc

Ví dụ mã C++

#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) { 
        Node *left_child = insert(node->left, key); 
        node->left = left_child; 
        left_child->parent = node; 
    } else if (key > node->data) { 
        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); 
}

Kết quả