二叉树关键名词

结点的度：结点拥有几个直接子树，那它的度就是几

树的度：树内各结点度的最大值

叶子结点：度为 0 的结点

非终端结点：度不为 0 的结点

孩子结点：原结点的子树的根结点被称为原结点孩子

双亲结点：原结点是其子树根结点的双亲

兄弟结点：同一个双亲的孩子结点之间互为兄弟结点

祖先结点：该结点往上经过根结点的那些结点成为祖先结点

子孙结点：类比祖先结点

层次：根在第一层，下面一次加一

堂兄弟结点：同一层的结点互成为堂兄弟结点

树的深度：树中结点层次的最大深度

几种二叉树

二叉树

二叉树中每个结点度都小于等于 2，并且子树有左右之分不可颠倒。二叉树先序遍历+中序遍历可以唯一确定一个二叉树，二叉树的中序遍历+后序遍历也可以唯一确定一颗二叉树

满二叉树

除了最大深度的结点的度全为 0 ，其他结点的度都是 2 的树，深度为 k，则结点数 2^k - 1

完全二叉树

完全二叉树有个特点就是二叉树中，对于任意一个双亲结点来讲，它的左子树的深度一定等于或者比右子树的深度大一层，最直观的就是完全二叉树最左边的一定是二叉树中最深的一条线路。

平衡二叉树

完全二叉树有个特点就是二叉树中，对于任意一个双亲结点来讲，它的左右子树深度之差的绝对值等于 0 或者 等于 1。完全二叉树一定是平衡二叉树。平衡二叉树的常用算法有红黑树，AVL，Treap，伸展树，SBT 等

二叉树有关的式子

深度为 n 的满二叉树的结点数

结点数 = 2^0 + 2^1 + 2^2 + …… + 2^(n-1) = 2^n - 1

深度为 n 的满二叉树的叶子结点数

叶子结点数 = 2^(n-1)

深度为 n 的满二叉树的非叶子结点数

非叶子结点数 = 2^(n-1) - 1

二叉树遍历

• 先序：根左右
• 中序：左根右
• 后序：左右根

为什么先序+中序可以确定一颗二叉树？

先序：E C D I K P O G

中序：D I C K E P O G

因为先序遍历可以确定根结点为 E，由于先序遍历是根左右，从先序中去找一个个的根，在中序中找根，就很容易了

为什么中序+后序可以确定一颗二叉树？

中序：D I C K E P O G

后序：I D K C G O P E

因为后序遍历可以确定根结点为 E，因为中序遍历根左边是左子树，根右边是右子树，所以比较后序可以找到左子树的末尾是 C，即为左子树的根，右子树的末尾为 E，这样递归下去，就可以找到所有的根了