《征服数据结构》二叉树

摘要：

1，二叉树的介绍

2，树的常见术语

3，二叉树的特性

1，二叉树的介绍

二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构，两个分支分别是左子树和右子树。除了根节点以外每个节点有且只有一个父节点，其中根节点没有父节点。

二叉树的种类非常多，根据不同的特性分为二叉搜索树，AVL树，红黑树，笛卡尔树，二叉堆，线段树，哈夫曼树等。

二叉树的节点可以为空，如果节点为空，就是空的二叉树。在一颗非空树中，如果度为 0 的节点(叶子节点)个数为 a ，度为 1 的节点个数为 b ，度为 2 的节点个数为 c ，我们可以找到他们的对应关系：

1，总的节点个数就是：a+b+c。

2，边的个数 e 就是：b+2*c。

3，总的节点个数又等于边的个数加 1 ：e+1。

4，由边的个数相等可以得到：a+b+c=b+2*c+1，整理一下就是 a = c + 1 。

也就是说在任何二叉树中叶子节点的个数都等于度为 2 的节点个数加 1 ，这在很多笔试中经常考到。

下面我们来分析一下，度为 2 的节点指向两个子节点，也就是说一个度为 2 的节点贡献的边数是 2 ，一个度为 1 的节点贡献的边数是 1 ，度为 0 的节点贡献的边数是 0 ，所以一颗二叉树中总的边数就是：度为 2 的节点个数*2+度为 1 的节点个数。

又因为一条边只能指向一个节点，而根节点是没有边指向它的，所以在二叉树中：边的个数+1=总的节点个数。