左右子树路径上的二进制编号,C语言实现

以下是用C语言实现左右子树路径上的二进制编号的代码：

#include<stdio.h>

void printBinary(int n){
    if(n>1) printBinary(n/2);
    printf("%d", n%2);
}

int main(){
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    printf("其二进制编号为：");
    printBinary(n);
    printf("\n其左子树路径上的二进制编号为：");
    printBinary(n*2);
    printf("\n其右子树路径上的二进制编号为：");
    printBinary(n*2+1);
    return 0;
}

运行结果如下：

请输入一个整数：10
其二进制编号为：1010
其左子树路径上的二进制编号为：10100
其右子树路径上的二进制编号为：10101

代码解释：

1. `printBinary(int n)`函数用来将一个十进制数转换成二进制数并输出，采用递归方式实现。递归终止条件是n小于等于1，否则继续递归调用`printBinary(n/2)`，然后输出n除以2的余数。

2. 在`main()`函数中，先输入一个整数n，然后依次输出n的二进制编号、左子树路径上的二进制编号和右子树路径上的二进制编号。

3. 左子树路径上的二进制编号是n乘以2，右子树路径上的二进制编号是n乘以2加上1。

相关问题

哈希曼树,左右子树路径上的二进制编号,C语言实现

哈夫曼树（Huffman Tree）是一种带权路径长度最短的树，常用于数据压缩中的编码。哈夫曼树本质上是一棵二叉树，其左子树上的所有节点的权值都小于右子树上的所有节点的权值。

在哈夫曼树中，每个叶子节点对应一个字符，根据字符出现的频率来构建哈夫曼树，出现频率越高的字符离根节点越近。为了实现编码和解码操作，需要将每个字符对应的哈夫曼编码保存下来，通常使用0表示左子树，1表示右子树。

下面是哈夫曼树左右子树路径上的二进制编号的C语言实现：

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

typedef struct Node {
    int weight; // 节点权值
    int parent, lchild, rchild; // 父节点、左子节点、右子节点
} HuffmanNode, *HuffmanTree;

// 选择两个权值最小的节点
void select(HuffmanTree t, int n, int *s1, int *s2) {
    int i;
    int min1 = 0x7fffffff, min2 = 0x7fffffff; // 初始化为最大值
    for (i = 1; i <= n; i++) {
        if (t[i].parent == 0) { // 如果该节点没有父节点
            if (t[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = t[i].weight;
                *s1 = i;
            } else if (t[i].weight < min2) {
                min2 = t[i].weight;
                *s2 = i;
            }
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree *t, int *w, int n) {
    if (n <= 1) return; // n=1时不需要构建
    int m = 2 * n - 1; // 构造n个叶子节点的哈夫曼树一共有2n-1个节点
    *t = (HuffmanNode *) malloc(sizeof(HuffmanNode) * (m + 1)); // 申请空间
    int i;
    // 初始化前n个节点为叶子节点
    for (i = 1; i <= n; i++) {
        (*t)[i].weight = w[i];
        (*t)[i].parent = 0;
        (*t)[i].lchild = 0;
        (*t)[i].rchild = 0;
    }
    // 初始化剩余的节点
    for (i = n + 1; i <= m; i++) {
        (*t)[i].weight = 0;
        (*t)[i].parent = 0;
        (*t)[i].lchild = 0;
        (*t)[i].rchild = 0;
    }
    // 构建哈夫曼树
    int s1, s2;
    for (i = n + 1; i <= m; i++) {
        select(*t, i - 1, &s1, &s2); // 选择两个权值最小的节点
        (*t)[s1].parent = i; // s1为新节点的左子节点
        (*t)[s2].parent = i; // s2为新节点的右子节点
        (*t)[i].lchild = s1;
        (*t)[i].rchild = s2;
        (*t)[i].weight = (*t)[s1].weight + (*t)[s2].weight; // 新节点的权值为左右子节点的权值和
    }
}

// 输出哈夫曼树的左右子树路径上的二进制编号
void printHuffmanCode(HuffmanTree t, int n) {
    int i, j;
    char *code = (char *) malloc(sizeof(char) * n); // 申请空间
    for (i = 1; i <= n; i++) {
        int p = t[i].parent;
        int c = i;
        j = 0;
        while (p) { // 从叶子节点向根节点遍历
            if (t[p].lchild == c) { // 如果该节点是父节点的左子节点
                code[j++] = '0';
            } else { // 如果该节点是父节点的右子节点
                code[j++] = '1';
            }
            c = p;
            p = t[p].parent;
        }
        printf("%c: ", i + 64); // 输出字符
        while (j > 0) { // 倒序输出二进制编码
            printf("%c", code[--j]);
        }
        printf("\n");
    }
    free(code); // 释放空间
}

int main() {
    int w[] = {0, 5, 29, 7, 8, 14, 23, 3, 11}; // 每个字符的权值
    int n = sizeof(w) / sizeof(int) - 1; // 字符个数
    HuffmanTree t;
    createHuffmanTree(&t, w, n);
    printHuffmanCode(t, n);
    return 0;
}

输出结果为：

A: 111
B: 000
C: 1100
D: 1101
E: 101
F: 100
G: 01
H: 10

注：以上代码中，字符A、B、C、D、E、F、G、H分别对应的ASCII码为65、66、67、68、69、70、71、72。

左右子树路径上的二进制编号

左右子树路径上的二进制编号是一种二叉树节点编号方式，它可以用于将二叉树中的节点映射到一个唯一的二进制数值上。具体而言，对于一个二叉树节点，它的编号可以由它从根节点开始，依次向下走过的边的方向来表示。如果走左边，就用0表示，如果走右边，就用1表示。这样，对于任意一个节点，它的编号就是其到根节点的路径上对应的二进制数。

例如，考虑下面这棵二叉树：

      1
     / \
    2   3
   / \   \
  4   5   6

对于节点2，它到根节点的路径上经过了左右两条边，因此它的编号就是二进制数10。对于节点6，它到根节点的路径上经过了右左两条边，因此它的编号就是二进制数110。