参考书籍:小灰的算法之旅

树和二叉树

树

如图：

在数据结构中，树的定义如下：
树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。
1.有且仅有一个特定的称为根的节点。
2.当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

如图：

树的最大层级数，被称为树的高度或深度。显然，上图这个树的高度是4。

二叉树

如图：

二又树节点的两个孩子节点，一个被称为左孩子（left child），一个被称为右孩子（right child）。这两个孩子节点的顺序是固定的，就像人的左手就是左手，右手就是右手，不能够颠倒或混淆。

满二叉树

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

如图：

完全二叉树

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

如图：

完全二叉树的条件没有满二叉树那么苛刻：满二又树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

二叉树的应用

二叉树包含许多特殊的形式，每一种形式都有自己的作用，但是其最主要的应用还在于进行查找操作和维持相对顺序这两个方面。

这里我们介绍一种特殊的二叉树：二叉查找树（binary search tree）。光看名字就可以知道，这种二叉树的主要作用就是进行查找操作。
二叉查找树在二叉树的基础上增加了以下几个条件。

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

如图：

二叉树的遍历

深度优先遍历

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。
前序遍历
二叉树的前序遍历，输出顺序是根节点、左子树、右子树。
中序遍历
二叉树的中序遍历，输出顺序是左子树、根节点、右子树。
后序遍历
二叉树的中序遍历，输出顺序是左子树、右子树、根节点。

广度优先遍历

如果说深度优先遍历是在一个方向上“一头扎到底”，那么广度优先遍历则恰恰相反：先在各个方向上各走出1步，再在各个方向上走出第2步、第3步.……一直到各个方向全部走完。听起来有些抽象，下面让我们通过二叉树的层序遍历，来看一看广度优先是怎么回事。

层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

二叉堆

二叉堆本质上是一种完全二叉树，它分为两个类型。

1.最大堆。
最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。
2.最小堆。
最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。

二叉堆的根节点叫作堆顶。

最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。