数据结构与算法 二叉树思维导图

由n(n>0)个有限结点组成的具有层次关系的集合

结点：树中的一个元素

结点的度：结点拥有的子树的个数，二叉树的度不大于2

树的度：树中最大结点度数

叶子：度为0的结点，也称为终端结点

高度：叶子结点的高度为1，根结点高度最高

层：根在第一层，以此类推

每个结点有零个或多个子结点

没有父结点的节点称为根结点

每一个非根结点有且只有一个父结点

除了根结点外，每个子结点可以分为多个不相交的子树

叶子节点一定要在最后一层，并且所有非叶子节点都存在左孩子和右孩子

从左到右、从上到下构建的二叉树；除了最后一层，都是满的，并且最后一层或者是满的，或者是右边缺少连续若干节点，成为完全二叉树

又称为二叉搜索树，排序二叉树，可为空树，或节点满足左子树所有节点<根节点<右子树，所有节点

是一种结构平衡的二叉搜索树，即叶子节点深度差不超过1，能够在$O(log n)$内完成插入、查找和删除操作,结构如图所示，常见的平衡二叉树有AVl树、红黑树等

又被称为高度平衡树，是最先发明的自平衡二叉查找树，任何节点的两个儿子子树的高度最大差别为1

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树

平衡前（非AVL树）

平衡后（AVL树）

结点是红色或者是黑色的

根结点是黑色的

每个叶子结点都是黑色的（NIL节点）

每个红色结点必须有两个黑色结点（从叶子到根节点的所有简单路径上不可能有两个连续的红色结点）