参考文章：https://zhuanlan.zhihu.com/p/351240279

一些基本概念

结点的度

一个结点含有的子结点个数称为该结点的度;

树的度

一棵树中，最大结点的度称为树的度;

父结点

若一个结点含有子结点，则这个结点称为其子结点的父结点;

深度

对于任意结点n,n的深度为从根到n的唯一路径长，根结点的深度为0;

高度

对于任意结点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0;

阶数

一个节点最多有多少个孩子节点。(一般用字母m表示)

关键字

节点上的数值就是关键字

树的特点

（1）每个结点或者无子结点或者只有有限个子结点;
（2）有一个特殊的结点,它没有父结点，称为根结点;
（3）每一个非根节点有且只有一个父节点;
（4）树里面没有环路

树的种类

按照有序性分

无序树

树中任意节点的子结点之间没有顺序关系

有序树

树中任意节点的子结点之间有顺序关系

按照节点包含子树个数

二叉树

每个节点最多含有两个子树的树称为二叉树;

二叉查找树 BST(Binary Sort/Search Tree)

又被成为二叉排序树。
首先它是一颗二叉树，若左子树不空，则左子树上所有结点的值均小于它的根结点的值;
若右子树不空，则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树;

满二叉树

描述1：叶节点除外的所有节点均含有两个子树的树被称为满二叉树
描述2：一棵深度为k且有(2^k-1)个结点的二叉树称为满二叉树
以上两种描述含义相同
根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有2^(i-1)个结点 (i≥1)

完全二叉树

如果一颗二叉树除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布
满二叉树是完全二叉树的特殊形态，即一棵树如果是满二叉树，那么必定是完全二叉树

霍夫曼树

带权路径最短的二叉树

红黑树

红黑树是一颗特殊的二叉查找树，每个节点都是黑色或者红色，根节点、叶子节点是黑色。
如果一个节点是红色的，则它的子节点必须是黑色的。

平衡二叉树(AVL)

一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

B树

B-树

B-树，也称为B树，是一种平衡的多叉树(可以对比一下平衡二叉查找树)，它比较适用于对外查找。
m阶B-数特征：
（1）根结点至少有两个子女;
（2）每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1.(⌈⌉表示向上取整)
（3）有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。
（4）所有的叶子结点都位于同一层。

B+树

B+树是B-树的变体，也是一颗多路搜索树。一棵m阶的B+树主要有这些特点：
（1）每个结点至多有m个子女;
（2）非根节点关键值个数范围：⌈m/2⌉ - 1 <= k <= m-1
（3）相邻叶子节点是通过指针连起来的，并且是关键字大小排序的。

B+树和B-树的主要区别

（1）B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
（2）B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
（3）查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
（4）B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。

二叉树遍历

先序、中序、后序遍历，其中每一层子树都按照此顺序

先序遍历

又称先根遍历，遍历顺序是根左右

中序遍历

又称中根遍历，顺序是左根右

后序遍历

又称后根遍历，顺序是左右根