键盘输入n值创建赫夫曼树

好的，我可以回答这个问题。要创建赫夫曼树，可以通过使用最小堆来实现。首先将所有的节点插入到最小堆中。然后，取出堆中最小的两个节点，将它们合并成一个新节点，并将新节点插入回最小堆中，直到最小堆中只剩下一个节点为止。这个最后剩下的节点就是赫夫曼树的根节点。在这个过程中，每个节点的权值都是其子树中节点权值之和。

相关问题

键盘输入n值创建赫夫曼树代码

好的，以下是键盘输入n值创建赫夫曼树的代码示例：

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

struct node {
    int freq;
    char symbol;
    struct node *left;
    struct node *right;
};

struct heap {
    int size;
    int capacity;
    struct node **array;
};

struct node *new_node(int freq, char symbol) {
    struct node *temp = (struct node*) malloc(sizeof(struct node));
    temp->freq = freq;
    temp->symbol = symbol;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

struct heap *create_heap(int capacity) {
    struct heap *new_heap = (struct heap*) malloc(sizeof(struct heap));
    new_heap->size = 0;
    new_heap->capacity = capacity;
    new_heap->array = (struct node**) malloc(capacity * sizeof(struct node*));
    return new_heap;
}

void swap_nodes(struct node **a, struct node **b) {
    struct node *temp = *a;
    *a = *b;
    *b = temp;
}

void min_heapify(struct heap *min_heap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < min_heap->size && min_heap->array[left]->freq < min_heap->array[smallest]->freq) {
        smallest = left;
    }
    if (right < min_heap->size && min_heap->array[right]->freq < min_heap->array[smallest]->freq) {
        smallest = right;
    }
    if (smallest != index) {
        swap_nodes(&min_heap->array[index], &min_heap->array[smallest]);
        min_heapify(min_heap, smallest);
    }
}

int is_size_one(struct heap *min_heap) {
    return (min_heap->size == 1);
}

struct node *extract_min(struct heap *min_heap) {
    struct node *min_node = min_heap->array[0];
    min_heap->array[0] = min_heap->array[min_heap->size - 1];
    min_heap->size--;
    min_heapify(min_heap, 0);
    return min_node;
}

void insert_min_heap(struct heap *min_heap, struct node *node) {
    min_heap->size++;
    int index = min_heap->size - 1;
    while (index && node->freq < min_heap->array[(index - 1) / 2]->freq) {
        min_heap->array[index] = min_heap->array[(index - 1) / 2];
        index = (index - 1) / 2;
    }
    min_heap->array[index] = node;
}

void build_heap(struct heap *min_heap) {
    int n = min_heap->size - 1;
    int i;
    for (i = (n - 1) / 2; i >= 0; i--) {
        min_heapify(min_heap, i);
    }
}

void print_codes(struct node *root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        print_codes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        print_codes(root->right, arr, top + 1);
    }

    if (!(root->left) && !(root->right)) {
        printf("%c: ", root->symbol);
        int i;
        for (i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

void huffman_codes(char data[], int freq[], int size) {
    struct node *left, *right, *top;
    struct heap *min_heap = create_heap(size);
    int i;
    for (i = 0; i < size; i++) {
        insert_min_heap(min_heap, new_node(freq[i], data[i]));
    }
    build_heap(min_heap);
    while (!is_size_one(min_heap)) {
        left = extract_min(min_heap);
        right = extract_min(min_heap);
        top = new_node(left->freq + right->freq, '$');
        top->left = left;
        top->right = right;
        insert_min_heap(min_heap, top);
    }
    int arr[100], top = 0;
    print_codes(extract_min(min_heap), arr, top);
}

int main() {
    int n, i;
    printf("Enter the number of characters: ");
    scanf("%d", &n);
    char data[n];
    int freq[n];
    printf("Enter the characters and their frequencies:\n");
    for (i = 0; i < n; i++) {
        scanf(" %c %d", &data[i], &freq[i]);
    }
    huffman_codes(data, freq, n);
    return 0;
}

希望能对你有所帮助！

codeblocks实现键盘输入n值创建赫夫曼树代码

以下是使用 codeblocks 实现键盘输入 n 值创建赫夫曼树的代码示例：

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

typedef struct node {
    int weight;             // 节点权值
    struct node *left;      // 左子树指针
    struct node *right;     // 右子树指针
} Node;

typedef struct heap {
    int size;               // 堆中节点数目
    Node **data;            // 存储节点指针的数组
} Heap;

// 创建一个新节点
Node *new_node(int weight) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->weight = weight;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建一个新的最小堆
Heap *new_heap(int max_size) {
    Heap *heap = (Heap *) malloc(sizeof(Heap));
    heap->size = 0;
    heap->data = (Node **) malloc(sizeof(Node *) * max_size);
    return heap;
}

// 合并两个最小堆，返回一个新的最小堆
Heap *merge(Heap *h1, Heap *h2) {
    Heap *heap = new_heap(h1->size + h2->size);
    int i = 0, j = 0, k = 0;
    while (i < h1->size || j < h2->size) {
        Node *node;
        if (i >= h1->size) {
            node = h2->data[j++];
        } else if (j >= h2->size) {
            node = h1->data[i++];
        } else if (h1->data[i]->weight < h2->data[j]->weight) {
            node = h1->data[i++];
        } else {
            node = h2->data[j++];
        }
        heap->data[k++] = node;
    }
    heap->size = k;
    return heap;
}

// 创建赫夫曼树
Node *huffman_tree(int n) {
    Heap *heap = new_heap(n);
    for (int i = 0; i < n; i++) {
        int weight;
        printf("请输入第 %d 个节点的权值：", i + 1);
        scanf("%d", &weight);
        heap->data[i] = new_node(weight);
        heap->size++;
    }

    while (heap->size > 1) {
        Node *left = heap->data[0];
        Node *right = heap->data[1];
        Node *parent = new_node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        heap->data[1] = parent;
        heap->size--;
        for (int i = 1; i < heap->size; i++) {
            heap->data[i] = heap->data[i + 1];
        }
        heap->data[0] = parent;
        for (int i = 0; i < heap->size - 1; i++) {
            if (heap->data[i]->weight > heap->data[i + 1]->weight) {
                Node *temp = heap->data[i];
                heap->data[i] = heap->data[i + 1];
                heap->data[i + 1] = temp;
            }
        }
    }

    Node *root = heap->data[0];
    free(heap->data);
    free(heap);
    return root;
}

int main() {
    int n;
    printf("请输入节点数目 n：");
    scanf("%d", &n);
    Node *root = huffman_tree(n);

    printf("赫夫曼树的前序遍历结果为：");
    pre_order(root);
    printf("\n");

    return 0;
}

注意，上述代码中的 `pre_order` 函数（用于前序遍历赫夫曼树）并未在代码中给出，你可以自己实现或者从网络上查找现成实现。