1. 前缀码判定

题目

前缀码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

请编写一个程序，判断输入的n个由1和0组成的编码是否为前缀码。如果这n个编码是前缀码，则输出"YES”；否则输出第一个与前面编码发生矛盾的编码。

输入：
第1行为n（表示下面有n行编码）
第2～n+1行为n个由0或1组成的编码

输出：判断结果

例如，如果输入：

5

00

01

10

110

111

每一个字符均不是其他字符编码的前缀，所以，输出：YES

再如，如果输入：

5

00

01

10

110

11

编码11与前面的编码110的前缀，所以，输出：11

C++代码

#include   
#include   
  
using namespace std;  
  
// 定义二叉树的节点，包含一个布尔型成员变量 is_end 和一个 TreeNode 指针数组 next  
struct TreeNode {  
    bool is_end;  // 布尔型变量，表示当前节点是否是一个字符串的结束  
    TreeNode* next[2];  // TreeNode 指针数组，表示下一个节点  
    TreeNode() : is_end(false) {  // 构造函数，初始化变量  
        next[0] = nullptr;  // 下一个节点的第一部分设为空  
        next[1] = nullptr;  // 下一个节点的第二部分设为空  
    }  
};  
  
// 插入函数：在二叉树中插入一个字符串  
bool insert(TreeNode* root, string& code) {  
    TreeNode* node = root;  
    for (int i = 0; i < code.size(); ++i) {  
        int index = code[i] - '0';  // 计算字符对应的索引  
        if (!node->next[index]) {  // 判断子节点是否为空  
            node->next[index] = new TreeNode();  
        }  
        node = node->next[index];  // 移动到下一个子节点  
        if (node->is_end) {  // 如果此节点是字符串的结束，则插入失败  
            return false;  
        }  
    }  
    node->is_end = true;  // 标记插入的字符串结束的位置  
    return !node->next[0] && !node->next[1];  // 插入成功条件是当前节点无子节点  
}  
  
// 主函数  
int main() {  
    int n;  
    cin >> n;  // 输入字符串的数量  
    TreeNode* root = new TreeNode();  // 创建新的二叉树  
  
    for (int i = 0; i < n; ++i) {  
        string code;  
        cin >> code;  // 读取待插入的字符串  
        if (!insert(root, code)) {  // 如果插入失败（返回 false）  
            cout << code << endl;  // 输出字符串  
            delete root;  // 释放内存  
            return 0;  // 程序错误退出  
        }  
    }  
  
    cout << "YES" << endl;  // 所有字符串都插入成功，输出：YES  
    delete root;  // 释放内存  
    return 0;  // 程序正常退出  
}  
跳至...