二叉树

二叉树是计算机科学中最基础且重要的树形数据结构。简单来说，它是一个有序的树，其中每个节点最多只能有两个子节点，分别称为左子节点和右子节点（左右顺序不能颠倒）

  • 基本术语：最顶层的节点叫根节点；没有子节点的节点叫叶子节点；每个节点到根节点有一条唯一的路径

  • 核心特性：二叉树具有递归性——每个节点的左子树和右子树本身也是一棵二叉树。这就意味着处理二叉树的问题，天然适合用递归算法来解决

实战案例

tree（二叉树）

pasted_1785926813652_2er60s.png

反编译定位 main 函数，将我们输入的值 v4 传入了 chkflag() 中

pasted_1785926944181_khavs5.png

进入函数，分析核心逻辑

pasted_1785927495159_b89ao8.png

函数开头固定了 flag 格式

1
strcpy(Str, "flag{xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx}");

每个 x 位置要求输入一个十六进制字符

1
2
3
if ( Str[i] == 120 ) // 120 = x

0 1 2 3 4 5 6 7 8 9 a b c d e f

每读到一个 x 位置，程序会把该字符转成 4 位二进制字符

1
2
3
4
5
case 'a':
  glockflag[4 * v4]     = 49; // '1'
  glockflag[4 * v4 + 1] = 48; // '0'
  glockflag[4 * v4 + 2] = 49; // '1'
  glockflag[4 * v4 + 3] = 48; // '0'

完整映射如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 -> 0000
1 -> 0001
2 -> 0010
3 -> 0011
4 -> 0100
5 -> 0101
6 -> 0110
7 -> 0111
8 -> 1000
9 -> 1001
a -> 1010
b -> 1011
c -> 1100
d -> 1101
e -> 1110
f -> 1111

所以 chkflag() 的本质是把 flag 中的 32 个十六进制字符展开成 128 位二进制串

继续往后分析 parse() 函数

pasted_1785929035504_jyl34g.png

明显是二叉树，循环 128 次（v5 <= 127）：

  • 按位移动：

    • 如果当前位是 '0'（ASCII 48）：v3 = *(v3 + 12)，即移动到左子节点

    • 如果当前位是 '1'（ASCII 49）：v3 = *(v3 + 16)，即移动到右子节点

  • 检查当前节点（*v3）：读取节点首字节

  • 判断是否为小写字母（> 96 且 <= 122）：

    • 如果是：将 *v3 这个字符存入 Str2，索引 v4 加一。最关键的一步：将当前节点 v3 重置回根节点 a1（表示一个字符合成完毕，准备解码下一个字符）

    • 如果不是：不输出字符，v3 保持当前节点，继续用下一个 bit 深入遍历

使用 strncmp 比较 Str2 和硬编码字符串 "zvzjyvosgnzkbjjjypjbjdvmsjjyvsjx"

parse(a1) 的参数 a1 是树根节点，所以这棵树一定在前面被构造，下一步就是分析 init() 函数

pasted_1785929547999_an0l4p.png

接下来是算法逻辑拆解，第一步：初始化 26 个叶子节点

代码首先从 &unk_404040 拷贝了 26 个 int 数值到局部数组 v1。这 26 个数就是 26 个小写字母 a~z 的权重

第二步：霍夫曼树构建循环

这是一个经典的 “寻找两个最小权重节点，合并为新节点” 的过程：

  • 寻找最小两个：循环遍历当前所有节点（v7 表示当前节点总数），找出两个未被合并（标志位为 0）且权重最小的节点：

    • v5 指向最小权重节点

    • v4 指向次小权重节点

终止条件：如果找不到第二个节点（v4 == -1），说明只剩下根节点了，跳出循环

合并节点：

  • 创建一个新节点（索引为当前的 v7）：

    • 左子节点设为最小节点 v5（存储在偏移 +12）

    • 右子节点设为次小节点 v4（存储在偏移 +16）

    • 新节点权重 = 两者权重之和

  • 将 v5 和 v4 的标志位设为 1（标记它们已合并）

  • 节点总数 v7 加 1

第三步：返回根节点

循环结束后，v5 存储的就是最后一次未被合并的节点（即整棵树的根节点）。函数将其地址赋值给全局变量 root 并返回

查看权重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
a: 3
b: 19
c: 27
d: 6
e: 15
f: 47
g: 42
h: 58
i: 6
j: 95
k: 25
l: 7
m: 18
n: 55
o: 30
p: 24
q: 22
r: 2
s: 105
t: 13
u: 4
v: 75
w: 23
x: 12
y: 38
z: 51

简单来说，init() 的任务就是

1
2
3
每次找两个最轻的东西，把它们绑在一起，变成一个新的更重的东西
然后继续找两个最轻的，再绑
一直绑到最后只剩一个整体

最后这个整体就是一棵树，假设现在只有 4 个字母，不是 26 个，一开始它们是分开的：

1
a(3)   b(5)   c(7)   d(10)

先找两个最轻的，把它们绑成一个新东西

1
ab(8)   c(7)   d(10)

树的样子是：

1
2
3
   ab(8)
   /   \
a(3)  b(5)

然后继续找两个最轻的，把它们绑起来

1
2
3
ab(8)   c(7)   d(10)

cab(15)

树变成：

1
2
3
4
5
   cab(15)
   /     \
c(7)    ab(8)
        /   \
     a(3)  b(5)

然后继续

1
d(10)   cab(15)

绑起来

1
root(25)

树变成

1
2
3
4
5
6
7
   root(25)
   /      \
d(10)    cab(15)
         /     \
      c(7)    ab(8)
              /   \
           a(3)  b(5)

规则是往左走 = 0，往右走 = 1

从 root 到每个字母的路，就是这个字母的编码

例如 a 就是 root -> 右 -> 右 -> 左，所以就是 110

编写脚本解出 Huffman 表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
weights = [
    3, 19, 27, 6, 15, 47, 42, 58, 6, 95,
    25, 7, 18, 55, 30, 24, 22, 2, 105, 13,
    4, 75, 23, 12, 38, 51
]

nodes = []

# 1. 初始化 a-z 这 26 个叶子节点
for i, w in enumerate(weights):
    nodes.append({
        "ch": chr(ord("a") + i),
        "weight": w,
        "left": None,
        "right": None,
        "used": False,
    })

count = 26

# 2. 模拟 init() 的 while 循环
while True:
    min1 = -1
    min2 = -1
    v1 = 9999
    v2 = 9999

    # 找未使用节点中最小和第二小的两个节点
    for i in range(count):
        if nodes[i]["used"]:
            continue

        if nodes[i]["weight"] < v1:
            v2 = v1
            min2 = min1
            v1 = nodes[i]["weight"]
            min1 = i
        elif nodes[i]["weight"] < v2:
            v2 = nodes[i]["weight"]
            min2 = i

    # 如果只剩一个节点，说明建树完成
    if min2 == -1:
        root = min1
        break

    # 新建父节点
    # 注意：最小的节点放 left，第二小的节点放 right
    nodes.append({
        "ch": None,
        "weight": nodes[min1]["weight"] + nodes[min2]["weight"],
        "left": min1,
        "right": min2,
        "used": False,
    })

    nodes[min1]["used"] = True
    nodes[min2]["used"] = True

    count += 1


# 3. 从 root 开始 DFS，生成编码表
codes = {}

def dfs(idx, path):
    node = nodes[idx]

    # 如果是字母节点，就记录它的编码
    if node["ch"] is not None:
        codes[node["ch"]] = path
        return

    # 左边记 0
    dfs(node["left"], path + "0")

    # 右边记 1
    dfs(node["right"], path + "1")


dfs(root, "")

for ch in sorted(codes):
    print(f"{ch} -> {codes[ch]}")

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
a -> 111010111
b -> 00010
c -> 11000
d -> 0111010
e -> 110011
f -> 0011
g -> 0010
h -> 1101
i -> 0111011
j -> 010
k -> 01111
l -> 1110100
m -> 111011
n -> 1011
o -> 11100
p -> 01101
q -> 00011
r -> 111010110
s -> 100
t -> 110010
u -> 11101010
v -> 1111
w -> 01100
x -> 011100
y -> 0000
z -> 1010

将 zvzjyvosgnzkbjjjypjbjdvmsjjyvsjx 转为二进制

1
10101111101001000001111111001000010101110100111100010010010010000001101010000100100111010111111101110001001000001111100010011100

然后每 4 位转为 Hex 最后得到 flag

1
flag{afa41fc8-574f-1248-1a84-9d7f7120f89c}