Chuyển cây nhị phân thành cây thỏa tính chất AND logic trong C++

Chuyển cây nhị phân thành cây mà mỗi nút có giá trị = AND logic của 2 nút con. Giá trị nút chỉ là 0 hoặc 1.

Chương trình C++

#include <bits/stdc++.h> 
using namespace std; 

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

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

void transform_tree(Node *root) {
    if (root == NULL) return;
    transform_tree(root->left);
    transform_tree(root->right);
    if (root->left != NULL && root->right != NULL)
        root->data = (root->left->data) & (root->right->data);
}

void print_tree(Node* root) {
    if (root == NULL) return;
    print_tree(root->left);
    printf("%d ", root->data);
    print_tree(root->right);
}

int main() {
    Node *root = newNode(0);
    root->left = newNode(1);
    root->right = newNode(0);
    root->left->left = newNode(0);
    root->left->right = newNode(1);
    root->right->left = newNode(1);
    root->right->right = newNode(1);
    
    printf("Before conversion:\n");
    print_tree(root);
    transform_tree(root);
    printf("\nAfter conversion:\n");
    print_tree(root);
    return 0;
}

Kết quả

Before conversion: 0 1 1 0 1 0 1
After conversion: 0 0 1 0 1 1 1

Giải thích

Cây gốc (inorder): 0 1 1 0 1 0 1 Sau chuyển đổi (post-order tính AND): - Nút lá giữ nguyên - Nút cha = left AND right - Gốc = 0 AND 1 = 0 (vì left subtree root=0, right subtree root=1)