什么是二叉树

1.什么是二叉树？
　　面试中总有公司会问到二叉树问题，你会不一定能通过面试，但是不会肯定不行，那二叉树到底是什么？
　　二叉树作为一种重要的树形结构类型，在实际应用中有着十分广泛的应用和重要的意义。因为从许多实际问题中抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能够简单地转换为二叉树形式，而且二叉树的存储结构及其算法都比较简单，因此我们将讨论关于二叉树的存储、运算及应用。
2.二叉树的性质
　　性质一：在二叉树的第i个点上至多有2i-1各基地单个节点。
　　性质二：深度为k的节点上至多有2k-1个节点（k≥1）。
　　性质三：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
　　性质四：具有n个结点的完全二叉树的深度为「log2n」+1。
　　性质五：如果对一棵有n个结点的完全二叉树（其深度为「log2n」+1）的结点按层序编号（从第1层到第「log2n」+1层，每层从左到右），则对任一结点i（1≤i≤n），有：
　　（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点「i/2」
　　（2）如果2i>n，则结点n无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i
　　（3）如果2i+1>n，则结点i无右孩子，否则其右孩子RCHILD(i)是结点2i+1
3.常见的二叉树
　　平衡二叉树：当且仅当任意节点的两棵子树的高度差不大于1的二叉树。
　　完全二叉树：除了最后一层外，其他层的节点数目都达到最大的二叉树。完全二叉树是平衡二叉树的一个特例，完全二叉树最后一层上的节点都是从左到右填充的。对于一颗k层的完全二叉树，其节点总数最少的情况是：最后一层只有一个节点，此时节点数目为：2k-1；其节点总数最多的情况是：最后一层节点数目达到最大，即满二叉树，此时节点数目为：2k-1。对于节点数目为k的完全二叉树，其深度为log2（k+1）：
　　满二叉树：所有层的节点数目均达到最大的二叉树。满二叉树是完全二叉树的一个特例。对于深度为k的满二叉树，其节点数目是：2k-1；对于节点数目为k的满二叉树，其深度为：log2（k+1）。

4.二叉树的储存
二叉树的储存方式一般有两种：顺序储存或者链式储存。
（1）顺序储存
　　二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在某个数组下标为i-1的分量中，然后通过一些方法确定结点在逻辑上的父子和兄弟关系。
　　完全二叉树和满二叉树采用顺序存储比较合适，节省空间且数组元素下标值能确定结点在二叉树中的位置和结点之间的关系。但对于一般二叉树，则需要添加一些并不存在的空结点，所以效率并不高。
　　顺序储存二叉树示意图：
　　
注意：
　　这种存储结构显然要从数组下标1开始存储树中的结点。同时也要注意区别树的顺序存储结构与二叉树的顺序存储结构。在树的顺序存储结构中，数组下标代表结点的编号，下标上所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了树中各结点之间的关系。
　　二叉树属于树，因此二叉树都可以用树的存储结构来存储，但树却不能都用二叉树的存储结构来存储。
（2）链式储存结构
顺序存储的空间利用率比较低，所以二叉树一般都采用链式存储结构。链式结构是指用一个链表来存储一棵二叉树，二叉树中的每个结点用链表的一个链结点来存储。

常用的二叉链表存储结构如下图所示：

注意：
在含有n个结点的二叉链表中，含有n+1个空链域。
使用不同的存储结构时，实现二叉树操作的算法也会不同，因此要根据实际应用场合选择合适的存储结构。
原文链接：https://blog.csdn.net/Tonywu2018/article/details/89480282
原文链接：https://blog.csdn.net/lipengfei0427/article/details/96000075