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

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

Phương pháp: Duyệt Inorder thông thường với biến static prev

Duyệt: trái → gốc → phải. Dùng biến static prev theo dõi nút trước. Nối prev-right = root, root-left = prev.

Chương trình C++

#include <iostream> 
using namespace std; 

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

void binarytodll(node *root, node **head) {
    if (root == NULL) return;
    static node* prev = NULL;
    // Cây con trái
    binarytodll(root->left, head);
    // Xử lý gốc
    if (prev == NULL)
        *head = root;
    else {
        root->left = prev;
        prev->right = root;
    }
    prev = root;
    // Cây con phải
    binarytodll(root->right, head);
}

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

void print_dll(node *node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->right;
    }
}

int main() {
    node *root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);
    node *head = NULL;
    binarytodll(root, &head);
    print_dll(head);
    return 0;
}

Kết quả

25 12 30 10 36 15

Giải thích

Cây gốc:

       10
      /  \
    12    15
   / \   /
 25  30 36