以buu的[WUSTCTF2020]level4为例讲讲二叉树

二叉树是什么？

二叉树是一种树形数据结构，在遍历搜索、堆和表达式的表达中有着重要作用，是一种较为重要的表达方式。一般在逆向当中不会遇到十分困难的二叉树题目(毕竟是acm的题型)，但仍然要了解。这种题型建议配合python食用，C语言写起来过于复杂繁琐。但总体上这种题型做起来非常公式模板化。

二叉树的主要结构为根、左子树、右子树、节点

1
2
3
4
5
6
    1 (根节点)
   / \
  2   3 (内部节点—至少有一个子节点的节点)
 / \   \
4   5   6 (节点4、5、6是叶节点—无子节点的节点)
(左子树) (右子树)

根，又称为根节点，是整个二叉树的起始，在二叉树的逆向当中有着重要作用，在逆向时一定要先确认根节点，因为这样才能确认左右子树，进而做题。

左/右子树，根节点左边顺下来的第一个内部节点的所有子节点称为左子树，反之称为右子树。

节点，如上表。

二叉树的主要遍历模式有四种：

1.前序遍历(preorder)： 根节点 -> 左子树 -> 右子树

2.中序遍历(inorder)： 左子树 -> 根节点 -> 右子树

3.后序遍历(postorder)： 左子树 -> 右子树 -> 根节点

4.层序遍历(levelorder)： 按层逐层从上到下、从左到右访问每个节点

但是请注意：二叉树与是否线性无关，只关乎遍历模式。

同时，二叉树有一个非常重要的性质：

当遇到二叉树并且已知两种遍历模式，那么就可以通过这两种遍历模式得到完整的树，并且推导出剩下的一个遍历模式，而这个剩下的遍历模式一定是正确的flag。

下面来看实战level4

附件只有一个 elf 文件，丢进IDA看main逻辑如下

可以看到出现了struct，*left，*right，基本就可以确定是二叉树，把IDA里的信息基本遍历了一遍没什么实际作用，丢进虚拟机里跑一下看能得到什么。

由于这道题是wustctf，所以根节点必然是w，那么就可以推导出 type1 是中序遍历， type2 是后序遍历，那么由二叉树的性质可知，flag必然为前序遍历所输出的字符串。

逆向脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
def PreOrder(Postorder,Inorder):
    length = len(Postorder)
    if length == 0:
        return 0
    root = Postorder[length-1]
    for i in range(length):
        if root == Inorder[i]:
            break
    print(root,end="")
    PreOrder(Postorder[0:i],Inorder[0:i])
    PreOrder(Postorder[i:length-1],Inorder[i+1:length])
PreOrder("20f0Th{2tsIS_icArE}e7__w","2f0t02T{hcsiI_SwA__r7Ee}")

以上代码可以简化为(以ABDEC为例，后序遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
PreOrder( D E B C A , D B E A C )
│
├── print A
│
├── PreOrder( D E B , D B E )      ← 左子树
│   ├── print B
│   ├── PreOrder( D , D )
│   │   └── print D
│   └── PreOrder( E , E )
│       └── print E
│
└── PreOrder( C , C )              ← 右子树
    └── print C

再结合上面的

1
2
3
4
5
6
    1 (根节点)
   / \
  2   3 (内部节点—至少有一个子节点的节点)
 / \   \
4   5   6 (节点4、5、6是叶节点—无子节点的节点)
(左子树) (右子树)

我们可以推测出遍历模式是处理每一个内部节点时都按照处理完整的二叉树的流程来处理，所以在ABDEC中的例子里会先打印D再打印E，所以ABDEC的二叉树为

1
2
3
4
5
    A
   / \
  B   C 
 / \   
D   E

同理可得level4的二叉树和flag。

再次提醒：二叉树的做题很公式化，模板化，记住这道题的代码再根据情况修改就能做出几乎所有的二叉树的题目。