树的一些概念

一、节点的度、深度

参见 https://github.com/Snailclimb/JavaGuide/blob/main/docs/cs-basics/data-structure/tree.md

二、二叉树

二叉树(Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

​ 二叉树的性质：

​ 性质1：在二叉树的第i层上至多有2^i-1个结点(i≥1)。

​ 性质2：深度为k的二叉树至多有2^k-1个结点，(k≥1)。

​ 性质3：对任何一棵二叉树T，如果其终端结点数为n₀,度为2的结点数为n₂，则n₀=n₂+1。

三、满二叉树和完全二叉树

四、二叉搜索树

二叉搜索树（又：二叉查找树，二叉排序树，Binary Search Tree，BST）

满足以下几个条件：

1.若它的左子树不为空，左子树上所有节点的值都小于它的根节点。

2.若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

3.任意结点的左、右子树也分别为二叉搜索树。

五、二叉平衡树

平衡二叉树又称AVL树

平衡二叉树是一棵二叉搜索树，且具有以下性质：

1.可以是一棵空树

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