二维矩形装箱算法之二叉树 C语言代码

以下是使用二叉树实现二维矩形装箱算法的C语言代码：

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

typedef struct node {
    int x, y, w, h;
    struct node *left;
    struct node *right;
} node;

node* new_node(int x, int y, int w, int h) {
    node* n = (node*) malloc(sizeof(node));
    n->x = x;
    n->y = y;
    n->w = w;
    n->h = h;
    n->left = NULL;
    n->right = NULL;
    return n;
}

node* insert_node(node *root, int w, int h) {
    if (root == NULL) {
        return new_node(0, 0, w, h);
    }

    node *new_node;
    new_node = insert_node(root->left, w, h);
    if (new_node != NULL) {
        return new_node;
    }

    return insert_node(root->right, w, h);
}

void print_tree(node *root) {
    if (root == NULL) {
        return;
    }

    printf("(%d,%d,%d,%d)\n", root->x, root->y, root->w, root->h);
    print_tree(root->left);
    print_tree(root->right);
}

int main() {
    node *root = NULL;

    root = insert_node(root, 200, 100);
    insert_node(root, 50, 50);
    insert_node(root, 100, 80);
    insert_node(root, 120, 50);

    print_tree(root);

    return 0;
}

这段代码使用了一个二叉树来表示矩形的布局。在插入一个新的矩形时，从根节点开始遍历树，如果当前节点已经被占用，则尝试将新矩形放到左子树中，如果左子树已经被占用，则尝试将新矩形放到右子树中。如果新矩形无法放置，则返回NULL。

在输出时，简单地对树进行先序遍历，并输出每个节点的位置和大小信息。