从一条线到一根枝
数组、链表、栈、队列——到目前为止每一种结构都是线性的：每个元素后面最多只有一个元素。但现实里许多东西并不排成一队。一个文件夹装着好几个文件夹，每个里面又装着更多。公司的组织架构有一个老板，下面是几名直接下属，再下面是他们的下属。一本书分成章，章又分成节。这一切底下的形状，就是 [[tree|树]]：一个节点指向好几个*孩子*，而每个孩子本身又是一棵更小的树的顶端。
注意计算机科学里这个有趣的颠倒：我们把树画成倒过来的。那个唯一的起点节点坐在最上面，叫作根；枝条朝*下*生长，伸向叶子。就是这样——树不过是用边连起来的一堆节点，顶上有一个特殊节点，而且任何地方都没有环（顺着边往下走，你永远回不到出发点）。
(1) <- root
/ \
(2) (3)
/ \ \
(4) (5) (6) <- leaves: 4, 5, 6
edges go DOWNWARD; 1 is the parent of 2 and 3.你会用到的词
树自带一套小小的亲属词汇，值得现在就钉牢，因为后面每一篇导读都要靠它。
- 根 — 顶端那个唯一的节点，是唯一没有父节点的。
- 父 / 子 — 若有一条边从 A 向下连到 B，则 A 是 B 的*父*，B 是 A 的*子*。除根以外，每个节点都恰好有一个父节点。
- 叶 — 没有孩子的节点；枝条的末端。
- 节点的深度 — 它距离根有几条边（根的深度为 0）。
- 树的高度 — 它最深那片叶子的深度；整棵树有几层那么高。
二叉树：最多两个孩子
一般的树允许一个节点有任意多个孩子，但贯穿这一整级台阶的主力是 [[binary-tree|二叉树]]：每个节点最多有两个孩子，整整齐齐地叫作*左*和*右*。这个利落的限制让二叉树既易于存储，又（如后面几篇所示）在查找和排优先级上强得惊人。在 C++ 里，一个节点不过是个小小的结构体，装着一个值和两个指针——而某个孩子是 `nullptr`，只表示“这边没有枝”。
struct Node {
int value;
Node* left = nullptr; // child on the left, or nullptr
Node* right = nullptr; // child on the right, or nullptr
};
// build a tiny tree: (1)
// / \
// (2) (3)
Node* root = new Node{1};
root->left = new Node{2};
root->right = new Node{3};用递归走遍这棵树
你要怎么*访问树里的每一个节点*？这正是上一级学的 [[dsa-recursion|递归]] 大放异彩的地方。关键洞见：二叉树本身就是*递归定义*的——它是一个节点，加上一棵左子树，加上一棵右子树，而每棵子树本身又是一棵二叉树。于是代码恰好照着这个形状写。要处理一棵树，你就处理这个节点，再递归进入每个孩子；基准情形是空树（`nullptr`），这时你什么也不做、直接返回。
唯一要选的，是你*在什么时候*处理这个节点——相对于它的孩子而言。在孩子之前处理 → *前序*。在左、右之间 → *中序*。在两个孩子之后 → *后序*。同样的三行，只是换了顺序——而每种顺序各有用处（下一篇你会看到，中序能把一棵搜索树按有序读出来）。
void inOrder(Node* n) {
if (n == nullptr) return; // base case: empty subtree
inOrder(n->left); // 1. all of the left subtree
std::cout << n->value << ' '; // 2. then THIS node
inOrder(n->right); // 3. then all of the right subtree
}
// pre-order: visit node BEFORE the two recursive calls
// post-order: visit node AFTER the two recursive calls
// for the tree (2) in-order -> 1 2 3
// / \ pre-order -> 2 1 3
// (1) (3) post-order-> 1 3 2