C++U5-11-特殊二叉树-526互联

学习目标

完全二叉树：二又树拥有的性质，在完全二叉树中都拥有

性质

练习1

练习2

练习3

编程题：[完全二叉树的叶子结点]

【算法分析】
递归，前序遍历输出。

【参考代码】
#include <iostream>
using namespace std;

const int SIZE = 1010;

struct node {
    int left, right, value;
};

node a[SIZE]; // 定义一个数组用于存储树的结点信息
int n; // 结点数量

// 递归函数，用于遍历树并输出叶子结点的值
void is_tree(int root) {
    // 当左孩子和右孩子都不存在时，说明是叶子结点，直接输出其值并返回
    if (a[root].left == 0 && a[root].right == 0) {
        cout << a[root].value << " ";
        return;
    }
    
    // 依次递归遍历左子树和右子树
    is_tree(a[root].left);
    is_tree(a[root].right);
}

int main() {
    cin >> n; // 输入结点数量
    for (int i = 1; i <= n; i++) {
        cin >> a[i].value >> a[i].left >> a[i].right; // 输入每个结点的值以及左右孩子的索引
    }
    is_tree(1); // 从根结点开始遍历树
    return 0;
}

这段代码定义了一个结构体 node 来表示树的结点。每个结点有一个值（value）以及左孩子（left）和右孩子（right）的索引。

在 is_tree 函数中，通过递归的方式遍历树。如果当前结点的左孩子和右孩子都不存在，即为叶子结点，则直接输出该结点的值。否则，继续递归遍历左子树和右子树。

在 main 函数中，首先输入结点数量（n），然后使用一个循环输入每个结点的值及其左右孩子的索引。最后，调用 is_tree 函数从根结点开始遍历树，并输出叶子结点的值。

希望这些注释能够帮助理解代码的功能和执行流程！

View Code

二叉搜索树

程序阅读题

二叉搜索树总结

哈夫曼树

哈夫曼树（Huffman Tree）是一种数据压缩算法，它的应用场景广泛，包括以下几个方面：

数据压缩：哈夫曼树被广泛应用于数据压缩领域。通过构建哈夫曼树并生成相应的哈夫曼编码，可以将原始数据中出现频率较高的字符用较短的编码表示，从而实现对数据的有效压缩。这种压缩方式在文本、图像、音频等数据文件的存储和传输中都得到了广泛应用。
网络传输：由于哈夫曼编码能够将数据进行高效压缩，它在网络传输中也有重要应用。通过将数据使用哈夫曼编码进行压缩，可以减少数据的传输量，提高传输效率，节省带宽。特别是在低带宽网络环境下，如移动通信网络和互联网传输中，哈夫曼编码能够显著提升传输速度。
文件存储：哈夫曼树的应用不仅局限于数据传输，还可以用于文件的存储。在存储大量文本文件时，使用哈夫曼编码进行压缩可以大大减少存储空间的占用。这在对大规模文本数据进行备份、归档或者存储容量受限的场景下非常有用。
数据通信：哈夫曼树的高效压缩特性使得它在数据通信领域也有广泛应用。例如，通过在传感器网络中使用哈夫曼编码对传感器数据进行压缩，可以减少数据的传输和存储需求，从而延长传感器网络的寿命。

总之，哈夫曼树的应用范围非常广泛，适用于需要对数据进行高效压缩和解压缩的场景，包括数据压缩、网络传输、文件存储和数据通信等领域。

哈夫曼树（Huffman Tree）是一种用于数据压缩的二叉树结构，它具有以下重要概念：