引入

我们学习了树、二叉树、以及森林的知识。我们直到遍历二叉树非常的方便，甚至学会了给二叉树增加线索，提高效率。那么问题来了，如果一棵树，不是二叉树，一个结点下有 N 个孩子，那么我们遍历和操作起来，就会很复杂，因为不知道这棵树是深度长还是宽度广，如果都能转换成二叉树来操作就爽了！今天我们就看看普通树和森林，如何转换成二叉树。

普通树转换为二叉树

既然二叉树最方便操作，我们如何能够将普通树转换成二叉树呢？

上面是一棵普通树，有三层，我们将这棵树转换成二叉树

60秒读全文

这是一篇在 Nintendo Switch 6.2.0系统上，将游戏数据和存档从 128G 内存卡 转移 到 256G 内存卡，转移成功后，下载的游戏数据及存档有被 Switch 系统认到，并可正常使用的。

引入

前天下了《任天堂明星大乱斗 特别版》的时候，发现自己去年11月买的 128G microSD 卡竟然满了，以为能用一段时间呢… 今天进入 Manage Software 一看《DOOM》竟然要 30G ，《异度之刃2》、《任天堂明星大乱斗 特别版》、《Diabol III》都要十几个 G ，所以入了 256 G 的新 microSD 卡，老卡就留着之后进军 Vlog 吧。
至于为什么要写这篇文章呢？因为发现网上流传的几种方法我复现都失败了，也算是记录一下，万一下次换 512G 的内存卡呢？废话不多说，老 128G microSD 卡换256G，游戏文件和存档该如何转移呢？我们接着看~

准备

我们在开始前，请确认下面的东西已经准备好了

• Nintendo Switch 主机一台。
• **老内存卡：**我的就是128G 的老卡，不要动里面的数据。
• **新内存卡：**不用提前格式化，等下会讲。
• **高速读卡器：**如果没有像我 110+G 要等死…
• **PC / Mac：**用于操作文件转移。

引入

上一节，我们试着解决了树在存储时空间浪费和没法找到双亲结点的问题，这一节，我们着重看一下如何用代码实现。这篇难度有一点大，请务必沉住气，认真仔细。

思路拆解

我们一步一步的拆解代码来看看。

创建树结构体

我们首先声明我们重新设计的线索二叉树结点

• char data 存放结点数据
• 左孩子、右孩子这个不用细说了吧，
• Ltag 和 Rtag 主要是判断左孩子和右孩子究竟是指向左右孩子还是前驱后继
• 我们定义结构体的时候，使用了 typedef
• 后面所有的 BiTNode 你可以理解为 struct BiTNode，代表该结构体
• 后面所有的 BiTree 你可以理解为 struct BiTNode *，代表结构体指针
• 注意上面有个星号哈！

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
    NodeState Ltag;
    NodeState Rtag;
}BiTNode,*BiTree;

引入

前面，我们说过，二叉树的遍历方法，以及如何使用代码创建二叉树并将三种遍历顺序都输出出来。如果你还对单链表有印象，我们会发现上节我们树的创建过程其实就是根结点指向左右子树，很像单链表指向唯一后继，对不对？还记得为什么我们要使用双向链表嘛？因为双向链表在找寻唯一前驱的时候方便。因此，二叉树也遇到了相同的问题，左右子树不知道自己的双亲是谁，我们该怎么解决呢？

问题

现在的二叉树

• 一个结点下，数据域和指针域
• 数据域，存放数据
• 指针域，指向该结点下的左右子树

问题一

如果我要找这个结点的双亲该怎么办呢？

• 麻烦了！我们要重新遍历这个棵二叉树
• 直到遇到这个结点，然后记录它得双亲

问题二

引入

上一节，我们详细说明了二叉树的 4 种遍历方式，根据根的位置不同，我们分为前序遍历、中序遍历和后序遍历以及最常用的层序遍历。今天我们就来实战一下， 看看如何建立一棵树，并且按照我们需要的方式遍历树上的结点。

需求

• 根据输入建立一棵二叉树
• 输出其前序遍历、中序遍历和后序遍历结果

代码分析

首先要构建一棵树，因为是二叉树，所以结构体中包含左右两棵子树

• 存放数据的data
• 存放左右子树的指针域

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

struct BiTNode{
    char data;   //用于存放结点数据
    struct BiTNode *Lchild;   //存放左孩子地址
    struct BiTNode *Rchild;   //存放右孩子地址
};

引入

这节课是二叉树的考试重点，通过什么样的方式遍历二叉树，这里需要把内容搞清楚，不要混淆。

二叉树遍历

二叉树遍历(traversing binary tree)，指的是

• 从根结点出发，按照某种次序
• 依次访问二叉树中的所有结点
• 使得每个结点都被访问一次，且仅有一次。

二叉树跟线性结构的不同

线性结构的便利，最多是

• 顺序
• 循环
• 双向
• 都是简单的遍历方式

树就不一样了

• 树的结点之间不存在唯一的前驱和后继这样的关系
• 一个结点后面会跟着左子树和右子树两个结点，不是唯一的
• 所以下一个结点的选择是不同的

二叉树的遍历方式

如果都是从左到右的话，遍历方式分为 4 种

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

引入

前面，我们学习了二叉树的五大特性，那么既然说了这么久的二叉树，是时候讲一讲二叉树的数据结构该如何定义了。

回顾

如果你忘了之前的内容，点击下面的链接回顾：
数据结构之树-树的存储结构（一）-学习笔记-47
数据结构之树-树的存储结构（二）-学习笔记-47

思考

根据我们之前讨论树的存储结构，我们可以直到，树和结点里面包含的元素可以很灵活，我们甚至可以将链式存储结构跟顺序存储结构结合在一起使用。因为这样表达树这个数据结构才方便。但是

• 二叉树是一种特殊的树，由于它的特殊性，使得
• 顺序存储结构和链式存储结构都可以轻松的实现二叉树

二叉树的顺序存储结构

引入

我们上节课我们讲了三条性质，从层数、层节点数、深度、总结点数、以及度的概念了解了二叉树的一些有趣的性质，今天我们继续看看，二叉树还有什么有趣的特性。

从节点数判断深度，从深度判断节点数

预习一下取整符号：

• $\left \lfloor 这是向下取整符号 \right \rfloor$
• $\left \lfloor 2.4 \right \rfloor=2$ 向下取整到2
• $\left \lceil 2.4 \right \rceil=3$ 向上取整到3

具有 n 个结点的完全二叉树的深度 K 为$\left \lfloor \log_{2}n \right \rfloor+1$

• n 表示完全二叉数的结点数，上面的图中 n=5
• 上图的完全二叉树的深度为：$\left \lfloor \log_{2}5 \right \rfloor+1$
• $2^n=5$然后 n 再加 1。
• $n \approx 2.3$，再加上向下取整$\left \lfloor 2.3 \right \rfloor=2$
• 得到$2+1=3$，这棵完全二叉树有 3 层

引入

我们介绍了树，介绍了树中使用最多的二叉树，以及一些特殊的二叉树。今天我们就来看看二叉树为什么很好的体现了树的特性，二叉树有哪些有趣的特点呢？

每一层最大的节点数

• 在二叉树的第 i 层，至多有$2^{i-1} (i \geq 1)$ 个结点
• 上面这张图中
• 第一层$2^0=1$个结点
• 第二层$2^1=2$个结点
• 第三层$2^2=4$个结点
• 第四层$2^3=8$个结点

引入

我们介绍了什么是二叉树、以及二叉树一些与众不同的特点，例如只能有两个孩子，两个孩子还分为左子树和右子树，那么今天我们来看看特殊的二叉树。

斜树

¡¡™
顾名思义，斜树一定要倾斜。也就是说，一棵树

• 只有左子树
• 只有右子树

这样就不是斜树了。