树与层次结构
二叉树
二叉树是最常见、也最有用的一种树形：每个节点最多有两个子节点，习惯上称为左子节点和右子节点。这种整齐的两路分叉足以表达极其丰富的思想，而且由于每个节点只持有两个指针，它存储成本低、也便于推理。
“左”和“右”并非可以随意互换的标签——它们是有含义的。在二叉搜索树中，左子树存放较小的键，右子树存放较大的键；在表达式树中，它们分别对应一个运算符的两个操作数。许多算法在二叉树上天然是递归的：要对整棵树做某件事，就对左子节点做、对右子节点做，再把结果合并——这种模式你会一再遇到。
一棵有 n 个节点的二叉树，当它既满又平衡时，可以矮到只有约 log2(n) 层；而当每个节点都只有一个子节点、退化成一条变相的链表时，则可高达 n 层。形状决定开销：大多数操作的耗时与树高成正比，所以让二叉树保持低矮就是关键所在——这正是平衡树和堆要解决的问题。
int countNodes(Node* root) {
if (root == nullptr) return 0; // empty subtree
return 1 // this node
+ countNodes(root->left) // + left side
+ countNodes(root->right); // + right side
}递归地数节点——几乎每个二叉树算法的共同骨架。
这里的“二叉”指两路分叉，与二进制数制无关——在树的语境下，简体作二叉、繁体作二元。
又称
另见