数据结构之二叉树(一)——绪论

前言

二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构，包括完全二叉树、满二叉树、二叉查找树、AVL树、红黑树等等。本文中对数据结构中二叉树的概念和用途进行了汇总，不求严格精准，但求简单易懂。

二叉树

定义

二叉树的每个节点至多只有2棵子树(不存在度大于2的节点)，二叉树的子树有左右之分，次序不能颠倒。

性质

• 1）在非空二叉树中，第i层的节点总数不超过2^(i-1), i >=1;
• 2）深度为h的二叉树最多有2^h-1个节点(h>=1)，最少有h个节点;
• 3）对于任意一棵二叉树，如果其叶节点数为N0，而度数(子节点个数)为2的节点总数为N2，则N0=N2+1;
• 4）给定n个节点，能构成h(n)种不同的二叉树，其中h(n)为卡特兰数的第n项，h(n)=C(2*n, n)/(n+1)。
• 5）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。

种类

完全二叉树： 若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。有如下几个性质：

• 1）具有n个节点的完全二叉树的深度为log2(n+1);
• 2）具有n个节点的完全二叉树各节点如果用顺序方式存储，则节点之间有如下关系：
  • 若i为节点编号且i>1，则其父节点的编号为i/2；
  • 如果2i<=n，则其左儿子（即左子树的根节点）的编号为2i；若2i>n，则无左儿子；
  • 如果2i+1<=n，则其右儿子的节点编号为2i+1；若2i+1>n，则无右儿子。

注：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

满二叉树：满二叉树一定是完全二叉树，要求除最后一层无任何子节点外，每一层上的所有节点都有两个子节点。也可以这样理解，除叶子节点外的所有节点均有两个子节点。节点数达到最大值，所有叶子节点必须在同一层上。有如下几个性质：

• 1）一颗树深度为h(h>=1)，最大层数为k(k>=1)，深度与最大层数相同，即k=h;
• 2）叶子数为2(h-1);
• 3）第k层的节点数是：2^(k-1);
• 4）总结点数是：2^k-1，且总节点数一定是奇数。

二叉查找树：二叉查找树（Binary Search Tree），又称为二叉排序树（Binary Sort Tree）。二叉查找树或者是一棵空树，或者是具有下列性质的二叉树：

• 1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
• 3）左、右子树也分别为二叉查找树；
• 4）没有键值相等的节点。

平衡二叉树：是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡二叉树应运而生了。一般来讲，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。在接下来几篇博文中，我会介绍几种常见的自平衡二叉树——AVL树和红黑树。

总结

本篇博文主要介绍了几种常见二叉树的定义和性质，可以帮助大家从整体上对二叉树有一个宏观的认识，接下来几篇博文，将带领大家继续深入了解二叉树，敬请期待~

推荐阅读

• 数据结构之二叉树(一)——二叉树遍历
• 数据结构之二叉树(二)——二叉查找树(待更新)
• 数据结构之二叉树(三)——AVL树(待更新)
• 数据结构之二叉树(四)——红黑树(待更新)

写在最后

欢迎大家关注我的个人博客复旦猿。