Chèn cây tìm kiếm nhị phân với con trỏ mẹ trong C ++

Chúng ta có thể chèn nút mới vào BST theo cách đệ quy. Trong trường hợp đó, chúng tôi trả về địa chỉ gốc của mỗi cây con. Ở đây chúng ta sẽ thấy một cách tiếp cận khác, nơi mà con trỏ cha sẽ cần được duy trì. Con trỏ chính sẽ hữu ích để tìm tổ tiên của một nút, v.v.

Ý tưởng là lưu trữ địa chỉ của các cây con bên trái và bên phải, chúng tôi thiết lập các con trỏ cha của các con trỏ được trả về sau khi gọi đệ quy. Điều này xác nhận rằng tất cả các con trỏ cha được đặt trong quá trình chèn. Cấp độ gốc của root được đặt thành null.

Thuật toán

chèn (nút, khóa) -

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

Ví dụ

#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);
}

Đầu ra