Data Structures

栈

• 后进先出

队列

• 先进先出

二叉树

二叉树性质：

1. 至多拥有两颗子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分。
2. 若二叉树的层次从0开始，则在二叉树的第i层至多有$2^i$个结点($i>=0$)。
3. 高度为k的二叉树最多有$2^{k+1} - 1$个结点$(k>=-1)$。 (空树的高度为-1)
4. 对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为$n$, 则$m = n + 1$。

完美二叉树

满二叉树,一个深度为$k(>=-1)$且有$2^{k+1} - 1$个结点的二叉树称为完美二叉树。

完全二叉树

完全二叉树从根节点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子节点都靠左对齐。

回溯算法