樹與層次結構
二元樹
二元樹是最常見、也最有用的一種樹形：每個節點最多有兩個子節點，習慣上稱為左子節點和右子節點。這種整齊的兩路分叉足以表達極其豐富的思想，而且由於每個節點只持有兩個指標，它儲存成本低、也便於推理。
「左」和「右」並非可以隨意互換的標籤——它們是有含義的。在二元搜尋樹中，左子樹存放較小的鍵，右子樹存放較大的鍵；在運算式樹中，它們分別對應一個運算子的兩個運算元。許多演算法在二元樹上天然是遞迴的：要對整棵樹做某件事，就對左子節點做、對右子節點做，再把結果合併——這種模式你會一再遇到。
一棵有 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
}遞迴地數節點——幾乎每個二元樹演算法的共同骨架。
這裡的「二元」指兩路分叉，與二進位數制無關——在樹的語境下，繁體作二元、簡體作二叉。
又稱
另見