数据结构和算法（6）

一、树

树的定义是：

树（tree）是n（n ≥0）个节点的有限集。当n =0时，称为空树。在任意一个非空树中，有如下特点。

1.有且仅有一个特定的称为根的节点。

2.当n >1时，其余节点可分为m （m >0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

如上图，节点1是根节点（root）；节点5、6、7、8、9是树的末端，被称为叶子节点（leaf）；虚线部分是根节点1的其中一个子树。

节点4的上一级节点，是节点4的父节点（parent）；从节点4衍生出来的节点，是节点4的孩子节点（child）；和节点4同级，由同一个父节点衍生出来的节点，是节点4的兄弟节点（sibling）。

树的最大层级数，称为树的高度或深度。

二、二叉树

二叉树（binary tree）是树的一种特殊形式，这种树的每个节点最多有2个孩子节点。

二叉树节点的两个孩子节点，一个被称为左孩子（left child），一个被称为右孩子（right child）。

此外，二叉树还有两种特殊形式，一个叫作满二叉树，另一个叫作完全二叉树。

一个二叉树的所有非叶子节点都存在左孩子和右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

二叉树编号从1到12的12个节点，和前面满二叉树编号从1到12的节点位置完全对应，所以是完全二叉树。 

满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全就行。

三、二叉树的存储结构

二叉树是属于逻辑结构，可以使用链式存储结构或者数组来表达。

链式存储是二叉树最直观的存储方式。

二叉树的每一个节点包含3个部分：

• 存储数据的data变量
• 指向左孩子的left指针
• 指向右孩子的right指针

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。

假设一个父节点的下标是parent，那么它的左孩子节点的下标就是2 × parent + 1；右孩子节点的下标就是2 × parent + 2 。

反过来，假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是（leftChild - 1）/ 2 。

四、二叉树的应用

1. 查找

进行查找操作的是使用二叉查找树（binary search tree）。

二叉查找树在二叉树的基础上增加了以下几个条件：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
• 如果右子树不为空，则右子树上所有节点的值均小于根节点的值。
• 左子树、右子树也都是二叉查找树

下图是个标准的二叉查找树。

例如查找值为4的节点，步骤如下：

a.访问根节点6，发现4<6；

b.访问节点6的左孩子节点3，发现4>3；

c.访问节点3的右孩子节点4，发现4=4，这正是要查找的节点。

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O（logn） ，和树的深度是一样的。 

 2.维持相对顺序

二叉查找树要求左子树节点的值小于父节点的值，右子树节点的值大于父节点的值，正是这样保证了二叉树的有序性。因此二叉查找树还有另一个名字——二叉排序树（binary sort tree）。

新插入的节点，同样要遵循二叉排序树的原则。例如插入新元素5，由于5<6、5>3、5>4，所以5最终会插到节点4的右孩子位置。

再如插入新元素10，由于10>6、10>8、10>9，所以10最终会插到节点9的右孩子位置。

除二叉查找树以外，二叉堆也维持着相对的顺序。不过二叉堆的条件要宽松一些，只要求父节点的值比它的左右孩子的值都大。