二叉树

在中文语境中，节点结点傻傻分不清楚，故后文以 node 代表 "结点"，root node 代表根节点，child node 代表 “子节点”

二叉树是诸多树状结构的始祖，至于为什么不是三叉树，四叉树，或许是因为计算机只能数到二吧，哈哈，开个玩笑。二叉树很简单，每个 node 最多存在两个 child node，第一个节点称之为 root node。

二叉树具备着一些基本的数学性质，不过很简单，定义从 i 从 0 开始：

• 第 i 层至多有 2i 个 node；
• 深度为 i 层二叉树至多有 2i+1-1 个 node。

二叉树的特殊类型

这里有兴趣的可以了解一下，不影响后文的阅读。二叉树根据 child node 的不同，衍生出了几种特殊类型：在一颗二叉树中，如果每个 node 都有 0 或 2 个 child node，则二叉树是满二叉树；定义从 i 从 0 开始，一棵深度为 i，且仅有 2i+1−1 个 node 的二叉树，称为完美二叉树；若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干 node，则此二叉树为完全二叉树。

二叉搜索树

二叉搜索树（Binary Search Tree），也叫二叉查找树，有序二叉树，排序二叉树（名字还挺多）。它是一种常用且特殊的二叉树，它具备一个特有的性质，left node（左结点）始终小于 parent node (父结点)，right node 始终大于 parent node。