二叉树的介绍

写在前面：

二叉树是数据结构课程中非常重要的内容，我们针对二叉树的概念、性质以及类型展开详细介绍。

一、概念

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者空集（称为空二叉树），或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。其中， 二叉树的最大度为2。

特点：
（1）每个结点最多有两棵子树；
（2）左子树和右子树是有顺序的；
（3）即使树中某结点只有一颗子树，也要区分左右；

图1 二叉树

例如：图1中的E结点，虽然只有一个子树，但是还是要区分左右，图中 I 为右子树。

二、性质

性质1：在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。
性质2：深度为k的二叉树至多有2^(k)-1个结点(k≥1)。
性质3：对任何一颗二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
性质4：具有n个结点的完全二叉树深度为⌊log2n⌋+1。
其中，满二叉树：深度为k且含有2^(k)-1个结点的二叉树。完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
性质5：如果对有一颗n个结点的完全二叉树（深度为⌊log2n⌋+1）的结点按层序编号（从第1层到第⌊log2n⌋+1层，每层从左到右），则对任一结点i(1≤i≤n)，有
（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点；
（2）如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i；
（3）如果2i+1>n，则结点i无右孩子（结点i为叶子结点）；否则其右孩子RCHILD(i)是结点2i+1。

三、类型

1.满二叉树
除了最后一层的节点没有任何子节点外，每层上的所有节点都有两个节点的二叉树

图2 满二叉树

2.完全二叉树
一颗二叉树的深度为h，除了第h层外，其他各层的节点都有两个子节点，且第h层的所有节点都集中在最左边
（满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树）

图3 完全二叉树

3.二叉搜索树
左子树的所有节点的值均小于它的根节点的值
右子树的所有节点的值均大于它的根节点的值
它的左右子树也分别为二叉搜索树

4.平衡二叉树
平衡二叉树是一颗高度平衡的二叉搜索树；左右两个子树的高度差绝对值不超过1，且左右两个子树都是平衡二叉树；
通过左旋右旋来实现平衡；

图4 平衡二叉树

图5 非平衡二叉树

5.红黑树
一种弱平衡的二叉搜索树
（1）每个结点要么是红的，要么是黑的
（2）根节点是黑的
（3）如果一个结点是红色的，那么它的两个子节点都是黑的
（4）每个叶节点都是黑的
（由于是弱平衡，可以看到，在相同的节点的情况下，AVL树的高度低于红黑树），相对于严格要求的AVL树来说，它的旋转次数少，所哟对于搜索，插入和删除操作较多的情况下，可以用红黑树。

6.堆
堆是完全二叉树，所以一定是平衡二叉树。
分为大顶堆和小顶堆
在大顶堆中：父节点的值比每一个子节点的值都要大
在小顶堆中：父节点的值比每一个子节点的值都要小

注意：堆的根节点中存放的是最大或者最小的元素，但是其他节点的排序是未知。例如：在一个大顶堆中，最大的那一个元素总是位于index 0的位置，但是最小的元素则未必是最后一个元素。唯一能保证的是最小的元素是一个叶节点，但是不确定是哪一个。

插入、删除、查找的时间复杂度：
二叉搜索树：最好logn 最坏n 【参考】
平衡二叉搜索树：logn
红黑树：logn

引用

[1]https://blog.csdn.net/AiTTTTTT/article/details/122923963
[2]http://data.biancheng.net/view/192.html
[3]https://blog.csdn.net/peachzy/article/details/116499139