Chuyển cây nhị phân thành danh sách liên kết đôi (Phương pháp 2) trong C++

Chuyển cây nhị phân thành danh sách liên kết đôi (DLL). Con trỏ left/right thành prev/next. Thứ tự DLL = inorder của cây.

Phương pháp: Duyệt inorder ngược (Reverse Inorder)

Duyệt: phải → gốc → trái. Tạo nút mới, di chuyển head pointer đến nút mới nhất. Tạo DLL từ cuối về đầu.

Chương trình C++

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

struct Node {
    int data;
    Node *left, *right;
};

void binary_todll(Node* root, Node** head_ref) {
    if (root == NULL) return;
    // Chuyển cây con phải
    binary_todll(root->right, head_ref);
    // Chèn gốc vào đầu DLL
    root->right = *head_ref;
    if (*head_ref != NULL)
        (*head_ref)->left = root;
    *head_ref = root;
    // Chuyển cây con trái
    binary_todll(root->left, head_ref);
}

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void print_dll(Node* head) {
    printf("Doubly Linked list:\n");
    while (head) {
        printf("%d ", head->data);
        head = head->right;
    }
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(3);
    root->right = newNode(6);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
    root->right->right = newNode(8);
    root->left->left->left = newNode(0);
    root->left->left->right = newNode(2);
    root->right->right->left = newNode(7);
    root->right->right->right = newNode(9);
    
    Node* head = NULL;
    binary_todll(root, &head);
    print_dll(head);
    return 0;
}

Kết quả

Doubly Linked list: 0 1 2 3 4 5 6 7 8 9

So sánh 2 phương pháp

• Phương pháp 1 (Set 1): Inorder thông thường, dùng biến static prev theo dõi nút trước
• Phương pháp 2 (Set 2): Reverse inorder, cập nhật head pointer, không cần biến static