1. 二叉树（Binary Tree)的定义
1.1 什么是二叉树（Binary Tree)
每个结点至多拥有两棵子树的树结构(即二叉树中不存在度大于2的结点)。并且，二叉树的子树有左右之分，其次序不能任意颠倒。
上面概念中提到了“度”的概念，“度”其实就是某个节点子节点的数量。如果某个节点的子节点数量为1，则该节点的度为1，如果有8个子节点，则度为8，以此类推。
1.2 二叉树的术语
除了二叉树的定义外，还有许多相关的术语。单纯介绍术语可能不容易理解，这里给出一幅图进行说明。
图1 二叉树的主要概念
下面是对二叉树中主要术语的解释：
结点的度（Degree）：结点的子树个数；
树的度：树的所有结点中最大的度数；
叶结点（Leaf）：度为0的结点；
父结点（Parent）：有子树的结点是其子树的根节点的父结点；
子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；
兄弟结点（Sibling）：具有同一个父结点的各结点彼此是兄弟结点；
路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；
祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；
子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；
结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；
1.3 二叉树的性质
我们设定二叉树的根节点为为第1层，则二叉树有如下性质。这些性质可以通过数学方式进行证明，但本文暂时不做证明，大家了解即可，对于理解后续概念有一些帮助：
性质1：二叉树第i层上最多有 2^（i-1） 个结点(i≥1)；
性质2：深度（高度）为k的二叉树至多有2^(k)-1个结点(k≥1，深度k也就是树的最大层级)；
性质3：包含n个结点的二叉树的深度（高度）至少为log2 (n+1)；
性质4：在任意一棵二叉树中，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。
1.4 二叉树的数据存储
二叉树在C语言中可以通过结构体表示，其定义的方式可以是如下：
struct bitree_node {
int b_data; //数据域，指向具体的数据
struct bitree_node *left; //指向左子节点
struct bitree_node *right; //指向右子节点
};
在这个实例中，为了简单，我们假设其存储的数据类型为整型数，当然最好的方式是void指针的形式。这样，二叉树就是一个通用的数据结构，可以存储任何类型的数据。
图2 二叉树的数据存储
2. 二叉树的特例
根据二叉树存储数据组织结构的差异，二叉树有很多特例。比如有些二叉树所有节点只有左子节点，或者非叶子节点的每个二叉树的节点都有2个子节点等等。下面我们分别进行介绍。
2.1 斜二叉树
只有左子节点或只有右子节点的二叉树称为斜二叉树。
图3 斜二叉树
2.2 完美二叉树
一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。完美二叉树也就是满二叉树，也就是所有非叶子节点都有2个叶子节点，并且每一次都是满的。如图所示：
图4 完美二叉树
2.3 完全二叉树(Complete)
完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
下图就不是一棵完全(Complete)二叉树
图5 完全二叉树
3. 二叉树相关的算法（面试题）
在面试和笔试的过程中，二叉树的题目是非常多的。除了常见的关于二叉树遍历的题目外，还有其它一些延伸的题目。本文今天先将二叉树相关的题目罗列到这里，后续会给出每个题目的解题思路和代码示例。
网友评论