二叉树关键名词

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

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

叶子结点：度为 0 的结点

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

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

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

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

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

子孙结点：类比祖先结点

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

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

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

几种二叉树

二叉树

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

满二叉树

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

完全二叉树

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

平衡二叉树

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