本文记录一下自己学习二叉树中的一些理解和感悟

首先介绍一下什么是二叉树

二叉树

满足以下两个条件的树就是二叉树：

  1. 本身是有序树（若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(Ordered Tree)）；
  2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。

二叉搜索树

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；

二叉平衡树

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有AVL树（二叉平衡搜索树），B树（多路平衡搜索树，2-3树，2-3-4树中的一种），红黑树等。

AVL 树 （二叉平衡搜索树）

AVL树（由发明者Adelson-Velsky 和 Landis 的首字母缩写命名），是指任意节点的两个子树（左右子树）的高度差不超过1的平衡树。又称自平衡二叉搜索树。

2-3 树

性质

  1. 满足二叉搜索树的性质性质
  2. 节点可以存放一个或两个元素性质
  3. 每个节点有两个或三个子节点

2-3-4 树

  1. 2节点：包含两个子节点和一个数据元素
  2. 3节点：包含三个子节点和一个数据元素
  3. 4节点：包含四个子节点和一个数据元素

2-3-4树，它的每个非叶子节点，要么是2节点，要么是3节点，要么是4节点，且可以自平衡，所以称作2-3-4树。

B树

B树，表示的是一类树，它允许一个节点可以有多于两个子节点，同时，也是自平衡的，叶子节点的高度都是相同的。

所以，为了更好地区分一颗B树到底属于哪一类树，我们给它一个新的属性：度（Degree）：一个节点能有多少箭头指向其他节点。

具有度为3的B树，表示一个节点最多有三个子节点，也就是2-3树的定义。
具有度为4的B树，表示一个节点最多有四个子节点，也就是2-3-4树的定义。

参考链接
动图演示：如何彻底理解红黑树