二叉树的一些基本概念汇总

 二叉树 ：二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点
（好像结点，节点均可；百度百科为结点，力扣官网为节点）

子树：只要包含了一个节点，就必须包含这个节点下的所有节点；
子结构：包含了一个节点，可以只取左子树或者右子树，或者都不取；
二叉树的深度（高度）：max(左子树深度，右子树深度)+1
节点的度：该节点的分支的个数 ：度为0,1,2
节点的种类：
  根节点
  叶子节点 :度为0
  分支节点 ：度不为0的节点
  孩子节点
  兄弟节点
  祖先节点
  子孙节点
满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1-h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布；否则就是非完全二叉树
平衡二叉树：平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1

1. 第i层最多有$2^{i-1}$个节点
2. 深度为h的二叉树，最多含有$2^h-1$个节点
3. 若在任意一棵二叉树中，有$n_0$个叶子节点，有$n_2$个度为2的节点，则必有$n_0$=$n_2$+1
4. 具有n个节点的完全二叉树深为$lo{g}_2^x+1$（其中x表示不大于n的最大整数）