แปลง Binary Tree เป็น Binary Search Tree ใน C++

โจทย์

ให้ Binary Tree (BT) ต้องการแปลงเป็น Binary Search Tree (BST) โดยคงโครงสร้างต้นไม้เดิมไว้

ความแตกต่าง BT และ BST

• Binary Tree: โหนดแต่ละตัวมีลูกได้สูงสุด 2 ตัว
• Binary Search Tree: Left < Root < Right, ทุก Subtree เป็น BST

วิธีแปลง (3 ขั้นตอน)

1. Inorder Traversal BT เก็บค่าในอาร์เรย์ arr[]
2. เรียง arr[] จากน้อยไปมาก
3. Inorder Traversal อีกครั้ง แทนค่าจาก arr[] เข้าโหนดทีละตัว

เหตุผล: Inorder ของ BST ให้ค่าเรียงน้อยไปมาก ดังนั้นการใส่ค่าที่เรียงแล้วกลับเข้าโครงสร้างเดิมจะได้ BST

ตัวอย่างโค้ด C++

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

void Inordertraversal(struct node* node, int inorder[], int* index_ptr) {
    if (node == NULL) return;
    Inordertraversal(node->left, inorder, index_ptr);
    inorder[*index_ptr] = node->data;
    (*index_ptr)++;
    Inordertraversal(node->right, inorder, index_ptr);
}

int countNodes(struct node* root) {
    if (root == NULL) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

void arrayToBST(int* arr, struct node* root, int* index_ptr) {
    if (root == NULL) return;
    arrayToBST(arr, root->left, index_ptr);
    root->data = arr[*index_ptr];
    (*index_ptr)++;
    arrayToBST(arr, root->right, index_ptr);
}

struct node* newNode(int data) {
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void printInorder(struct node* node) {
    if (node == NULL) return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main() {
    struct node* root = NULL;
    root = newNode(17);
    root->left = newNode(14);
    root->right = newNode(2);
    root->left->left = newNode(11);
    root->right->right = newNode(7);
    printf("Inorder Traversal of the binary Tree:\n");
    printInorder(root);
    int n = countNodes(root);
    int* arr = new int[n];
    int i = 0;
    Inordertraversal(root, arr, &i);
    qsort(arr, n, sizeof(arr[0]), compare);
    i = 0;
    arrayToBST(arr, root, &i);
    delete[] arr;
    printf("\nInorder Traversal of the converted BST:\n");
    printInorder(root);
    return 0;
}

ผลลัพธ์

Inorder Traversal of the binary Tree: 11 14 17 2 7
Inorder Traversal of the converted BST: 2 7 11 14 17